글 읽기 - 볼록껍질 예외케이스 부탁드립니다.

kkpos0206 6년 전 0

문제상황 수정해도 제 프로그램이 계속 18%에서 틀립니다.

추가로 예외 케이스 있으면 좀 알려주세요

좌표정렬 -> 기준점에서 반시계 정렬

-> 볼록 판정 순서로 작성하였습니다.

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

struct point{
 long long x;
 long long y;
 point (long long _x, long long _y) : x(_x), y(_y) {}
 point () {}
 point operator- (const point &k){
 return point (x-k.x,y-k.y);
 }
 long long cross(const point &k){
 return x*k.y - y*k.x;
 }
 long long dist(){
 return x*x + y*y;
 }
};

point ix;

bool compare1 (point left, point right){ // 반시계 정렬
return (left-ix).cross(right-ix)>0;
}
bool compare2 (point& left, point& right){ 
 return (left.y!=right.y) ? left.y < right.y : left.x < right.x;//y좌표가 가장 작고 그중 x좌표가 가장 작은점
}
bool prev(point new_p, point here_p){ // 볼록 판정
long long val = here_p.cross(new_p);
 if(val > 0) return false;
 else if(val == 0 && new_p.dist() < here_p.dist()) return false;
 return true;
}

long long convexhull(vector<point> pi){
 vector<point> res;
 sort(pi.begin(),pi.end(),compare2);//좌표정렬
ix = pi[0];

sort(pi.begin()+1,pi.end(),compare1);//반시계정렬

res.push_back(pi[0]);
 res.push_back(pi[1]);

 int i = 2; 
 while(i<pi.size()){ //볼록판정
while(res.size()>=2&&prev(pi[i]-res[res.size()-2], res.back()-res[res.size()-2])==true){ res.pop_back(); }
 res.push_back(pi[i]); 
 i++;
 }
 return res.size();
}

int main(){ 

int n;
 scanf("%d",&n);
 vector<point> v(n,point ());
 int i;
 long long x, y;
 for(i=0;i<n;i++){
 scanf("%lld%lld",&x,&y);
 v[i].x = x;
 v[i].y = y;
 }
 printf("%d",convexhull(v));

return 0;
}

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

문제

문제

출처

ICPC

볼록껍질 예외케이스 부탁드립니다.

kkpos0206 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말