글 읽기 - 볼록 껍질 도움 바랍니다ㅠㅠ

112ckek 3년 전 0

1. x좌표, y좌표로 정렬하여 기울기로 정렬

2. i는 현재 추가하려는 좌표

idx와 idx - 1과 idx - 2는 이미 추가된 좌표로

point 1,2,3에 ccw를 수행해 ccw라면 idx + 1에 추가, 아니라면 point 0, 1, 3에 ccw를 수행해서 일직선 혹은 내부의

점 포함 방지, 둘다 아니라면 point 2를 point 3으로 교체

질문글 tc 다해봤는데 다 맞네요ㅠㅠ 도움 바랍니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#define f first
#define s second
using namespace std;
using ll = long long;
const double MAX = 1e5;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n; cin >> n;
    vector<pair<double, double>> v(n);
    for(ll i = 0; i < n; i++)
        cin >> v[i].f >> v[i].s;
    sort(v.begin(), v.end()); // x오름차순, y오름차순으로 정렬
    vector<tuple<double, double, double>> slope(n); // (기울기, x, y)
    for(ll i = 1; i < n; i++){
        if(v[i].f == v[0].f) slope[i - 1] = {MAX, v[i].f, v[i].s}; // 수직선은 기울기 10만으로 처리
        else slope[i - 1] = {(v[i].s - v[0].s) / (v[i].f - v[0].f), v[i].f, v[i].s};
    }
    slope[n - 1] = {MAX + 1, 0, 0};
    sort(slope.begin(), slope.end());
    ll k = 1;
    while(get<0>(slope[0]) == get<0>(slope[k])) k++;
    v[1] = {get<1>(slope[k - 1]), get<2>(slope[k - 1])};
    v[2] = {get<1>(slope[k]), get<2>(slope[k])};
    ll idx = 2;
    for(ll i = k + 1; i < n - 1; i++){
        ll x0, y0; tie(x0, y0) = v[idx - 2];
        ll x1, y1; tie(x1, y1) = v[idx - 1];
        ll x2, y2; tie(x2, y2) = v[idx];
        ll m3, x3, y3; tie(m3, x3, y3) = slope[i];
        if((x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1) > 0) v[++idx] = {x3, y3}; // ccw면 점 추가
        
        
        //      a
        //    b c
        //  d e f g 와 같은 경우 처리
        // d->g->c->b->a 에서 c 자리를 a로 대신
        else if((x1 - x0) * (y3 - y1) - (x3 - x1) * (y1 - y0) <= 0) v[--idx] = {x3, y3}; 
        else v[idx] = {x3, y3};
    }
    cout << idx + 1 << '\n';
    for(int i = 0; i < idx + 1; i++)
        cout << v[i].f << ' ' << v[i].s << '\n';
    return 0;
}

dohoon 3년 전 1

실제 답 : 6, 질문자님 답 : 7

도움이 되길 바랍니다.

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

문제

문제

출처

ICPC

볼록 껍질 도움 바랍니다ㅠㅠ

112ckek 3년 전 0

dohoon 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말