Mai intai trebuie sa te autentifici.

Cod sursa(job #1262921)

Utilizator ZimmyZimmermann Erich Zimmy Data 13 noiembrie 2014 17:59:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#define N 120010
#define X first
#define Y second
#define punct pair<double,double>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
punct P[N],Q;
int n,i,j,crit(punct,punct);
double det(punct,punct,punct),dist(punct,punct);
int main()
{
    fin>>n;
    for(i=0;i<n;i++)
    {
        fin>>P[i].X>>P[i].Y;
        if(P[i]<P[0]){Q=P[i];P[i]=P[0];P[0]=Q;}
    }
    sort(P+1,P+n,crit);
    for(j=1,i=2;i<n;i++)
    {
        while(det(P[j-1],P[j],P[i])<=0)j--;
        j++;P[j]=P[i];
    }
    fout<<j+1<<'\n';
    for(i=0;i<=j;i++)
        fout<<fixed<<setprecision(7)<<P[i].X<<' '<<P[i].Y<<'\n';

    return 0;
}
double det(punct A,punct B,punct C)
{
    return A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X;
}
double dist(punct A,punct B)
{
    return (A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y);
}
int crit(punct A,punct B)
{
    double d=det(P[0],A,B);
    if(d>=0.00000001)return 1;
    if(d<=-0.00000001)return 0;
    return dist(P[0],A)<dist(P[0],B);
}