글 읽기 - 반례는 다 맞는데 13%에서 틀립니다. 재채점의 고통에서 벗어나게 해주세요

loypyx 1년 전 0

3번의 재채점으로 맞았던 코드가 한번씩 다시 틀렸습니다. 두 번은 어디서 틀렸는지 찾았는데, 마지막엔 모르겠습니다.

오버플로우도 아니고, 동일선상의 점도 잘 고려한 것 같은데, 어디서 틀린걸까요?

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
struct ja{long long x,y;}q[100100];
long long ch(ja a,ja b,ja c){
//    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    return a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);
}
bool c(ja a,ja b){
    if(a.y==b.y)return a.x<b.x;
    else return a.y<b.y;
}
bool c2(ja a,ja b){
    long long t=ch(q[0],a,b);
    if(t<0)return false;
    if(t>0)return true;
    if(t==0)return abs(q[0].x-a.x)<abs(q[0].x-b.x);
}
int main(){
    long long n;cin>>n;
    stack<ja> s;
    for(int i=0;i<n;i++)cin>>q[i].x>>q[i].y;
    sort(q,q+n,c);
    sort(q+1,q+n,c2);
    s.push(q[0]);s.push(q[1]);
    for(int i=2;i<n;i++){
        while(s.size()>1){
            ja a=s.top();
            s.pop();
            ja b=s.top();
            if(ch(b,a,q[i])>0){
                s.push(a);break;
            }
        }
        s.push(q[i]);
    }
    cout<<s.size();
}

wjh5597486 1년 전 0

13% 저도 틀렸어서 다른 분들 참고 하시라고 올려드립니다.

제 코드는 해당 반례 해결하니 정답처리 되었습니다.

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

문제

문제

출처

ICPC

반례는 다 맞는데 13%에서 틀립니다. 재채점의 고통에서 벗어나게 해주세요

loypyx 1년 전 0

wjh5597486 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말