Cod sursa(job #1174076)

Utilizator teoionescuIonescu Teodor teoionescu Data 21 aprilie 2014 22:22:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<algorithm>
#define ll long long
#define ld long double
#define x first
#define y second
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Nmax = 120001;
typedef pair<ld,ld> point;
point v[Nmax],S[Nmax];
int N,K;
ld cp(point A,point B,point C){return A.x*B.y - A.y*B.x + B.x*C.y - B.y*C.x + C.x*A.y - C.y*A.x;}
bool cmp(point A,point B){return cp(v[1],A,B)<0;}
int main(){
    in>>N;
    for(int i=1;i<=N;i++) in>>v[i].x>>v[i].y;
    sort(v+1,v+N+1);
    sort(v+2,v+N+1,cmp);
    S[++K]=v[1];
    S[++K]=v[2];
    for(int i=3;i<=N;i++){
        while(K>=2 && cp(S[K-1],S[K],v[i])>0) K--;
        S[++K]=v[i];
    }
    out.precision(6);
    for(int i=K;i>=1;i--) out<<fixed<<S[i].x<<' '<<S[i].y<<'\n';
    return 0;
}