글 읽기 - 왜 시간초과가 나는 거죠?

impri 4년 전 0

각 점을 지나는 직선의 기울기를 저장 후 이진탐색으로 풀었는데 시간초과가 나네요.O(N^2logN)같은데 왜 그런거죠?

#include<bits/stdc++.h>

using namespace std;

int main(void){
int n;
int dots[1501][2];
vector<pair<int,int> >slope[1501];
long long result=0;
cin >> n;
for(int i=1;i<=n;i++)
    cin >> dots[i][0] >> dots[i][1];
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
     if(i==j)continue;
        if(dots[i][0]==dots[j][0])
        slope[i].push_back({0,0});
        else if(dots[i][1]==dots[j][1])
        slope[i].push_back({0,1});
        else{
            int dx=dots[i][0]-dots[j][0];
            int dy=dots[i][1]-dots[j][1];
            if(dx>0 && dy>0){
                int gc=__gcd(dx,dy);
                slope[i].push_back({dy/gc,dx/gc});
            }
            else if(dx<0 && dy<0){
                dx=-dx;
                dy=-dy;
                   int gc=__gcd(dx,dy);
                slope[i].push_back({dy/gc,dx/gc});
            }
            else{
                dx=abs(dx);
                dy=abs(dy);
                  int gc=__gcd(dx,dy);
                 slope[i].push_back({-dy/gc,dx/gc});
            }

        }
    }
}
for(int i=1;i<=n;i++)
    sort(slope[i].begin(),slope[i].end());

for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){

          int dx=dots[i][0]-dots[j][0];
          int dy=dots[i][1]-dots[j][1];
          swap(dx,dy);
          dy=-dy;
          if(dx==0)
          result+=(long long)(upper_bound(slope[j].begin(),slope[j].end(),make_pair(0,0))-lower_bound(slope[j].begin(),slope[j].end(),make_pair(0,0)));
          else if(dy==0)
         result+=(long long)(upper_bound(slope[j].begin(),slope[j].end(),make_pair(0,1))-lower_bound(slope[j].begin(),slope[j].end(),make_pair(0,1)));
          else{
            if(dx>0 && dy>0){
                int gc=__gcd(dx,dy);
result+=(long long)(upper_bound(slope[j].begin(),slope[j].end(),make_pair(dy/gc,dx/gc))-lower_bound(slope[j].begin(),slope[j].end(),make_pair(dy/gc,dx/gc)));
            }
            else if(dx<0 && dy<0){
                dx=-dx;
                dy=-dy;
                   int gc=__gcd(dx,dy);
        result+=(long long)(upper_bound(slope[j].begin(),slope[j].end(),make_pair(dy/gc,dx/gc))-lower_bound(slope[j].begin(),slope[j].end(),make_pair(dy/gc,dx/gc)));
            }
            else{
                dx=abs(dx);
                dy=abs(dy);
                  int gc=__gcd(dx,dy);
           result+=(long long)(upper_bound(slope[j].begin(),slope[j].end(),make_pair(-dy/gc,dx/gc))-lower_bound(slope[j].begin(),slope[j].end(),make_pair(-dy/gc,dx/gc)));
            }
          }
    }
}
cout << result/2;
}

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

문제

문제

출처

ICPC

왜 시간초과가 나는 거죠?

impri 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말