제출 #1362909

#제출 시각아이디문제언어결과실행 시간메모리
1362909AndreyPatrol Robot (CCO25_day2problem2)C++17
25 / 25
141 ms92656 KiB
#include<bits/stdc++.h>
using namespace std;

vector<pair<long long,long long>> haha(1);
vector<pair<long long,long long>> ans(0);

long long s(pair<long long,long long> a, pair<long long,long long> b) {
    return (a.first+b.first)*(b.second-a.second);
}

long long ori(pair<long long,long long> a, pair<long long,long long> b, pair<long long,long long> c) {
    return s(a,b)+s(b,c)+s(c,a);
}

bool compa(pair<pair<long long,long long>,long long> a, pair<pair<long long,long long>,long long> b) {
    long long x1 = a.first.first,x2 = b.first.first;
    long long y1 = a.first.second,y2 = b.first.second;
    if(y1*y2 < 0) {
        if(y1 > 0) {
            return true;
        }
        else {
            return false;
        }
    }
    if(y1*y2 == 0) {
        if(y1 == 0 && y2 == 0) {
            if(x1 > 0) {
                return true;
            }
            else {
                return false;
            }
        }
        if(y1 == 0) {
            if(x1 > 0 || y2 < 0) {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            if(x2 > 0 || y1 < 0) {
                return false;
            }
            else {
                return true;
            }
        }
    }
    return (x1*y2 > x2*y1);
}

void dude(vector<long long> wut) {
    if(wut.size() == 2) {
        ans.push_back({wut[0],wut[1]});
        return;
    }
    pair<pair<long long,long long>,long long> sm = {{LLONG_MAX,LLONG_MAX},0};
    for(long long i = 0; i < wut.size(); i++) {
        sm = min({{haha[wut[i]].second,haha[wut[i]].first},i},sm);
    }
    sm = {{sm.first.second,sm.first.first},sm.second};
    vector<pair<pair<long long,long long>,long long>> idk(0);
    for(long long i = 0; i < wut.size(); i++) {
        if(i != sm.second) {
            long long x = haha[wut[i]].first-sm.first.first;
            long long y = haha[wut[i]].second-sm.first.second;
            idk.push_back({{x,y},wut[i]});
        }
    }
    sort(idk.begin(),idk.end(),compa);
    long long p = -1;
    for(long long i = 1; i < idk.size()-1; i++) {
        if(ori(haha[idk[i-1].second],haha[idk[i].second],haha[idk[i+1].second]) < 0) {
            p = idk[i].second;
        }
    }
    if(p == -1) {
        ans.push_back({wut[sm.second],idk[0].second});
        ans.push_back({wut[sm.second],idk[idk.size()-1].second});
        for(long long i = 1; i < idk.size(); i++) {
            ans.push_back({idk[i].second,idk[i-1].second});
        }
        return;
    }
    vector<pair<pair<long long,long long>,long long>> yo(0);
    for(long long v: wut) {
        if(v != p) {
            long long x = haha[v].first-haha[p].first,y = haha[v].second-haha[p].second;
            yo.push_back({{x,y},v});
            yo.push_back({{-x,-y},-v});
        }
    }
    sort(yo.begin(),yo.end(),compa);
    vector<vector<long long>> banana(0);
    vector<long long> wow(0);
    for(long long i = 0; i < yo.size(); i++) {
        if(yo[i].second > 0) {
            wow.push_back(yo[i].second);
        }
        else {
            if(wow.size() > 0) {
                banana.push_back(wow);
            }
            wow.clear();
        }
    }
    if(banana.size()%2 == 1) {
        for(long long v: wow) {
            banana[0].push_back(v);
        }
    }
    else {
        banana.push_back(wow);
    }
    for(vector<long long> w: banana) {
        w.push_back(p);
        dude(w);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,a,b;
    cin >> n;
    for(long long i = 0; i < n; i++) {
        cin >> a >> b;
        haha.push_back({a,b});
    }
    vector<long long> wut(0);
    for(long long i = 1; i <= n; i++) {
        wut.push_back(i);
    }
    dude(wut);
    cout << ans.size() << "\n";
    for(pair<long long,long long> v: ans) {
        cout << v.first << " " << v.second << "\n";
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…