글 읽기 - 시간초과가 나오는 이유가 무엇일까요?

heeda0528 3년 전 0

구조체를 이용하여 x좌표, y좌표, 4분면 상의 위치를 저장하고, x축 양의 방향을 기준으로 반시계 방향으로 정렬해줍니다. 그런 뒤 차례대로 검사하면서 각도가 같은 과녘의 수를 세어 최대를 구하였습니다.

제가 생각하기론 정렬의 시간복잡도 O(nlogn), 검사의 시간복잡도 O(n)이고, 무한루프가 생길만한 구간도 없는 것 같습니다. 특별히 무거운 연산도 없는데 28% 부근에서 계속 시간초과가 납니다... 혹시 제가 놓치고 있는 부분이 무엇인지 알려주실 수 있나요?

#include<bits/stdc++.h>
using namespace std;
struct arr{
    int x,y,t;
}s[100001];
bool cmp(arr a,arr b)
{
    if(a.t==b.t)return 1LL*a.y*b.x<=1LL*b.y*a.x;
    return a.t<b.t;
}
int main()
{
    int n,m=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&s[i].x,&s[i].y);
        if(!s[i].y&&s[i].x>0)s[i].t=1;
        if(s[i].y>0&&s[i].x>0)s[i].t=2;
        if(s[i].y>0&&!s[i].x)s[i].t=3;
        if(s[i].y>0&&s[i].x<0)s[i].t=4;
        if(!s[i].y&&s[i].x<0)s[i].t=5;
        if(s[i].y<0&&s[i].x<0)s[i].t=6;
        if(s[i].y<0&&!s[i].x)s[i].t=7;
        if(s[i].y<0&&s[i].x>0)s[i].t=8;
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;){
        int cnt=1,j;
        for(j=i+1;s[i].t==s[j].t&&j<n;j++){
            if(1LL*s[i].y*s[j].x==1LL*s[j].y*s[i].x)cnt++;
            else break;
        }
        i=j;
        m=max(m,cnt);
    }
    printf("%d",m);
}

kimcoding 3년 전 0

sort의 비교함수 cmp을 다음과 같이 수정해야 합니다.

자세한 내용은 밑 링크를 참고하시면 될 것 같아요

https://stackoverflow.com/ques...

bool cmp(arr a,arr b)
{
    if(a.t==b.t)return 1LL*a.y*b.x < 1LL*b.y*a.x;
    return a.t<b.t;
}

heeda0528 3년 전 0

친절한 답변 감사합니다!

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

문제

문제

출처

ICPC

시간초과가 나오는 이유가 무엇일까요?

heeda0528 3년 전 0

kimcoding 3년 전 0

heeda0528 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말