Pagini recente » Cod sursa (job #530972) | Cod sursa (job #805851) | Cod sursa (job #2478401) | Cod sursa (job #2843623) | Cod sursa (job #2756385)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120001;
const double eps=1.0e-14;
struct POINT
{
double x,y;
};
POINT P[NMAX+5],LL;
int h[NMAX+5];
double cp(POINT &a, POINT &b, POINT &c)
{
return 1.0*(b.x - a.x) * (c.y - b.y) - 1.0*(b.y - a.y) * (c.x - b.x);
}
int ccw(POINT &a, POINT &b, POINT &c)
{
double val_cp;
val_cp = cp(a, b, c);
if (fabs(val_cp) < eps)
return 0;
if (val_cp >= eps)
return 1;
return -1;
}
bool cmp(POINT &A, POINT &B)
{
return ccw(LL,A,B)>0;
}
int main()
{
int n,i,top;
double x,y;
fin>>n>>x>>y;
P[0].x=x;
P[0].y=y;
for(i=1;i<n;i++)
{
fin>>x>>y;
P[i].x=x;
P[i].y=y;
if(fabs(y-P[0].y)<eps)
{
if(x-P[0].x<=-eps)
{
swap(P[0],P[i]);
}
}
else
{
if(y-P[0].y<=-eps)
{
swap(P[0],P[i]);
}
}
}
LL=P[0];
sort(P+1,P+n,cmp);
P[n]=P[0];
h[0]=0;
h[1]=1;
top=1;
i=2;
while(i<=n)
{
if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
{
h[++top]=i;
i++;
}
else top--;
}
fout<<top<<'\n';
for(i=0;i<top;i++)
{
fout<<fixed<<setprecision(12)<<P[h[i]].x<<" "<<P[h[i]].y<<'\n';
}
return 0;
}