Mai intai trebuie sa te autentifici.
Cod sursa(job #1262921)
Utilizator | 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);
}