Cod sursa(job #2127267)

Utilizator miguelMihail Lavric miguel Data 10 februarie 2018 15:12:27
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
const double r=45/atan(1);
int n;
pair <double, double> p[120001];
vi hull;

int orient(pi t, pi q, pi r){
    double v=(q.y-t.y)*(r.x-q.x)-(r.y-q.y)*(q.x-t.x);
    if(v==0) return 0;
    if(v>0) return 2;
    return 1;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin>>n;
    int l=0;
    p[0].x=INT_MAX;

    for(int i=1; i<=n; i++){
        cin>>p[i].x>>p[i].y;
        if(p[i].x<p[l].x ||(p[i].x==p[l].x && p[i].y<p[l].y)){
            l=i;
        }
    }

    int t=l, q;
    hull.pb(t);

    do{
        q=(t+1)%(n+1);
        if(q==0) q++;
        for(int i=1; i<=n; i++){
            if(orient(p[t], p[i], p[q])==2) q=i;
        }
        hull.pb(q);
        t=q;
    }while(t!=l);

    cout<<hull.sz-1<<'\n';
    for(int i=hull.sz-1; i>=0; i--){
        cout<<fixed<<setprecision(12)<<p[hull[i]].x<<" "<<p[hull[i]].y<<'\n';
    }
}