Pagini recente » Cod sursa (job #1107390) | Cod sursa (job #834010) | Cod sursa (job #1302913) | Cod sursa (job #391617) | Cod sursa (job #1355976)
//Convex Hull - O(NlogN)
#include <fstream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define Precizie 1000000000000LL
#define eps 0.0000000000001
#define Nmax 120009
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,k;
struct point {double x,y;}P[Nmax],st[Nmax];
bool Equal(double x,double y)
{
if(fabs(x-y)<eps) return 1;
else return 0;
}
bool LessThan(double x, double y)
{
if(1LL*Precizie*x<1LL*Precizie*y) return 1;
else return 0;
}
double CrossProduct(point A,point B,point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool cmp(point A, point B)
{
return LessThan(0,CrossProduct(P[1],A,B));
}
void ConvexHull()
{
sort(P+2,P+1+N,cmp);
k=2;
st[1]=P[1];
st[2]=P[2];
for(int i=3;i<=N;++i)
{
while(k>=2 && LessThan(CrossProduct(st[k-1],st[k],P[i]),0)) --k;
st[++k]=P[i];
}
}
int main()
{
int j=1;
f>>N;
f>>P[1].x>>P[1].y;
for(int i=2;i<=N;++i)
{
f>>P[i].x>>P[i].y;
if(LessThan(P[i].y,P[j].y)) j=i;
else if(Equal(P[i].y,P[j].y)&& LessThan(P[i].x,P[j].x)) j=i;
}
swap(P[1],P[j]);
ConvexHull();
g<<k<<'\n';
g.precision(6);
for(int i=1;i<=k;++i)
g<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
f.close();g.close();
return 0;
}