글 읽기 - 왜 시간초과일까요...

smu201111192 7년 전 0

정사각형이 되려면 2개의 대각선의 길이와 2개의 대각선의 중점이 같은점을 이용해서

가능한경우중에 제일긴 (대각선^2)/2 를 출력해주는식으로 작성해봤는데

시간초과가나네요... 왜그럴까요

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
#define mp make_pair
int getDistance(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}//대각선*대각선

int main(){
    int testcase;
    scanf("%d",&testcase);
    for(int t=1;t<=testcase;t++){
        int maxi=0;
        int n;scanf("%d",&n);
        pair<int,int> p[3000];
        map<pair<int,pair<double,double> >,int > m;
        m.clear();
        for(int i=0;i<n;i++){
            scanf("%d %d",&p[i].first,&p[i].second);
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int distance=getDistance(p[i].first,p[i].second,p[j].first,p[j].second);
                if(distance>maxi){
                int count=m[mp(-distance,mp((p[i].first+p[j].first)/2.0,(p[i].second+p[j].second)/2.0))]++;
                if(count>=1&&distance>maxi){
                    maxi=distance;
                }
                    
                }
            }
        }
        
        printf("%d\n",maxi/2);
    }
    
    
    return 0;
}

ntopia 7년 전 0

일단 "정사각형이 되려면 2개의 대각선의 길이와 2개의 대각선의 중점이 같은점"

이건 직사각형도 이걸 만족합니다.

따라서 이걸로 해결이 안될거고요,

그리고 시간복잡도가 n^2 * logn 면 연산량이 많으면 시간초과가 날 수도 있을 것 같습니다.

double형을 사용하지 않는게 하나의 방법이 될 수 있겠네요

smu201111192 7년 전 0

아하 너무쉽게 생각했네요 감사합니다~~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 시간초과일까요...

smu201111192 7년 전 0

ntopia 7년 전 0

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말