Cod sursa(job #664029)

Utilizator paulyBereschi Paul pauly Data 19 ianuarie 2012 15:02:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef struct{
double x,y;
} str;
str v[120005];
int i,n,p,k,S[120005];
double xm,ym,X,Y;
bool cmp(str x,str y)
{
    return (double)((y.y-Y)*(x.x-X))<(double)((y.x-X)*(x.y-Y));
}
bool coliniare(str x,str y,str z)
{
    double sol=x.x*y.y+y.x*z.y+z.x*x.y-x.y*y.x-y.y*z.x-z.y*x.x;
    return sol>0;
}
int main()
{
    ifstream fi("infasuratoare.in");
    ofstream fo("infasuratoare.out");
    fi>>n;
    xm=ym=int(2e9);
    for(i=1;i<=n;i++)
    {
        fi>>v[i].x>>v[i].y;
        if(v[i].x<xm) { xm=v[i].x; ym=v[i].y; p=i; } else
        if(v[i].x==xm and v[i].y<ym) { ym=v[i].y; p=i; }
    }
    X=v[p].x; Y=v[p].y;
    swap(v[p],v[n]);
    sort(v+1,v+n,cmp);
    for(i=1;i<=n;i++) if(X==v[i].x and Y==v[i].y) p=i;
    S[++k]=p;
    for(i=1;i<=n;i++)
    {
        if(i==p) continue;
        while(k>=2 and coliniare(v[S[k-1]],v[S[k]],v[i])) k--;
        S[++k]=i;
    }
    fo<<k<<"\n";
    fo<<fixed;
    fo<<setprecision(6);
    for(i=k;i>0;i--) fo<<(double)(v[S[i]].x)<<" "<<(double)(v[S[i]].y)<<"\n";
    return 0;
}