Cod sursa(job #1956083)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 6 aprilie 2017 14:44:04
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define rd(x) cin >> x;
#define rda(a,n) for(int i=1;i<=n;i++) cin >> a[i];
#define wr(x) cout << x << ' ';
#define wrl(x) cout << x << '\n';
#define wra(a,n) for(int i=1;i<=n;i++) cout << a[i] << ' '; cout << '\n';
#define lg length()
#define pb(x) push_back(x)
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
struct comp{
    bool operator()(int a, int b){
        return a>b;
    }
};

int n,bst;
double x[120005],y[120005];
pair<int,double> a[120005];
vector <int> p;

bool comp(pair<int,double> a, pair<int,double> b){
    return a.y<b.y;
}

int main(){
    ios_base :: sync_with_stdio(0);
    in >> n;
    x[0]=1e9+5; y[0]=1e9+5;
    for(int i=1;i<=n;i++) {
        in >> x[i] >> y[i];
        if(x[i]<x[bst]) bst=i;
        else if(x[i]==x[bst] && y[i]<y[bst]) bst=i;
    }
    for(int i=1;i<=n;i++){
        a[i].x=i;
        if(i!=bst){
            if(y[i]<y[bst]) a[i].y=atan((x[i]-x[bst])/(y[bst]-y[i]));
            else if(y[i]==y[bst]) a[i].y=90;
            else a[i].y=180-atan((x[i]-x[bst])/(y[i]-y[bst]));
        }
        else{
            a[i].y=1000;
        }
    }
    sort(a+1,a+n+1,comp);
    //for(int i=1;i<=n;i++) cout << a[i].x << ' ';
    p.pb(bst); p.pb(a[1].x); int t=1;
    for(int i=2;i<n;i++){
        while(((x[p[t]]-x[p[t-1]])*(y[a[i].x]-y[p[t-1]])-(y[p[t]]-y[p[t-1]])*(x[a[i].x]-x[p[t-1]]))<=0) p.pop_back(),t--;
        p.pb(a[i].x); t++;
    }
    out << t+1 << '\n';
    for(int i : p) out << fixed << setprecision(6) << x[i] << ' ' << y[i] << '\n';
}