Cod sursa(job #1956219)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 6 aprilie 2017 16:29:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 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;
pair<double,double> a[120005];
vector <int> p;

bool comp(pair<double,double> n, pair<double,double> m){
    return (n.x-a[1].x)*(m.y-a[1].y)-(n.y-a[1].y)*(m.x-a[1].x)>0;
}

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