Cod sursa(job #1066264)

Utilizator teoionescuIonescu Teodor teoionescu Data 24 decembrie 2013 13:23:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define abs(x) ((x)>=0?(x):-(x))
#define ll long long
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Nmax = 120002;
const double prc = 1e-12;
int N;
bool equal(double a,double b){
    return abs(a-b)<prc;
}
struct Point{
    double x,y;
    bool operator < (Point a){
        if( equal(x,a.x) ) return y<a.y;
        else return x<a.x;
    }
} v[Nmax],S[Nmax]; int K;
double det(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 det(v[1],a,b) < 0;
}
int main(){
    in>>N;
    for(int i=1;i<=N;i++){
        in>>v[i].x>>v[i].y;
    }
    for(int i=1;i<=N;i++){
        if(v[i]<v[1]) swap(v[i],v[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>=3 && det(S[K-1],S[K],v[i]) > 0 ) K--;
        S[++K]=v[i];
    }
    out<<K<<'\n';
    out.precision(9);out<<fixed;
    for(int i=K;i>=1;i--) out<<S[i].x<<' '<<S[i].y<<'\n';
    return 0;
}