글 읽기 - 어디가 잘못되었을까요 도와주세요

(追記) (追記ここまで)

어디가 잘못되었을까요 도와주세요

4181번 - Convex Hull

hyun0404woo 4년 전 0

solve()함수에서

x좌표순으로 정렬하고, 0번째 좌표를 기준으로 상대좌표들을 구하고

상대 좌표에 대해서 각도정렬을 했습니다.

→ ↑ ← ↓ 순으로 정렬되고

↓ 부분에 속하는 좌표들을 '하나의 선분 위에 있으면 거리가 작은게 우선이 되는 규칙' 때문에

순서를 뒤집어야 한다고 이해했습니다

어디가 잘못되었을까요ᅲ 도와주세요

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
struct Point{
 ll x, y;
 ll p, q;
 Point(ll x = 0, ll y = 0) : x(x), y(y), p(0), q(0) {}
};
int N, S;
Point convex[100001];
int CCW(const Point &p1, const Point &p2, const Point &p3){
 ll res = (p1.x*p2.y + p2.x*p3.y + p3.x*p1.y) - \
 (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y);
 if(res > 0) return 1; //반시계
 else if(res < 0) return -1; //시계
 else return 0;
}
ll det(const Point &p1, const Point &p2){
 ll res = (p1.p * p2.q - p1.q * p2.p);
 return res;
}
bool angle_sort(Point &p1, Point &p2){
 if(p1.p != 0 || p1.q != 0 || p2.p != 0 || p2.q != 0){
 if(det(p1, p2) > 0){
 return true;
 }
 else if(det(p1, p2) == 0){
 return p1.p*p1.p + p1.q*p1.q < p2.p*p2.p + p2.q*p2.q;
 }
 else{
 return false;
 }
 }
 if(p1.x == p2.x){
 return p1.y < p2.y;
 }
 else return p1.x < p2.x;
}
void solve(){
 
 sort(convex, convex+S, angle_sort);
 for(int i = 1; i < S; i++){
 convex[i].p = convex[i].x - convex[0].x;
 convex[i].q = convex[i].y - convex[0].y;
 }
 
 sort(convex+1, convex+S, angle_sort);
 
 int r;
 for(r = S-1; convex[r].x == convex[0].x; r--);
 r++;
 reverse(convex + r, convex + S);
 
 cout << S << "\n";
 for(int i = 0; i < S; i++){
 cout << convex[i].x << " " << convex[i].y << "\n";
 }
}
void input(){
 cin >> N;
 int a, b, k = 0;
 char c;
 for(int i = 0; i < N; i++){
 cin >> a >> b >> c;
 if(c == 'N') continue;
 convex[k++] = Point(a, b);
 }
 S = k;
}
int main(){
 input();
 solve();
 return 0;
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC