글 읽기 - 그래함 스캔 질문좀...(반례)

Rose 5년 전 0

그래함 스캔에서 좌표 각 정렬할때 벡터의 외적값으로 각의 크고작음을 판단하여서 정렬하였습니다.

혹시 반례를 찾아주실수있으신가요???

부탁드리겠습니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct P{
    long long x,y,vx,vy;
};
vector<P>spot;
vector<pair<long long,long long> >s;
int cmp1(P a1,P a2){
    return a1.y<a2.y;
}
int vcmp(P a1,P a2){
    return (1LL*a1.vx*a2.vy-1LL*a1.vy*a2.vx)>0;
}
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    long long temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    }else {
        return 0;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        P t={a,b,0,0};
        spot.push_back(t);
    }
    sort(spot.begin(),spot.end(),cmp1);
    for(int i=1;i<n;i++){
        spot[i].vx=spot[i].x-spot[0].x;
        spot[i].vy=spot[i].y-spot[0].y;
    }
    sort(spot.begin()+1,spot.end(),vcmp);
    s.push_back({spot[0].x,spot[0].y});
    s.push_back({spot[1].x,spot[1].y});
    int next=2;
    while(next<n){
        while(s.size()>=2){
            pair<int,int>fi,se;
            fi=s.back();
            s.pop_back();
            se=s.back();
            
            if(ccw(se.first,se.second,fi.first,fi.second,spot[next].x,spot[next].y)){
                
                s.push_back(fi);
                break;
            }
            
        }
        s.push_back({spot[next].x,spot[next].y});
        next++;
    }
    printf("%d",s.size());
    return 0;
}

Rose 5년 전 1

세가지 문제가 있었는데,

점정렬할때 y기준으로만 한점

벡터의 외적으로 각도정렬할때 평행할경우 (외적이 0인경우 (sin값이 0일때)) 고려안한점

형변환연산을 제대로이해안한점 이 있었습니다,

해결되었습니다.

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

문제

문제

출처

ICPC

그래함 스캔 질문좀...(반례)

Rose 5년 전 0

Rose 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말