Pagini recente » Cod sursa (job #1424648) | Cod sursa (job #2421691) | Statisticile problemei Fotbal | Cod sursa (job #943592) | Cod sursa (job #1404043)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point
{
double x,y;
};
const double eps=1.e-14;
point ll;
double cp(point a, point b, point c)
{
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
int ccw(point a, point b, point c)
{
double p=cp(a,b,c);
if(fabs(p)<eps)
//ABC coliniare
return 0;
if(p>=eps)
//C la stanga lui AB (trigonometric)
return 1;
//C la dreapta lui AB (clockwise)
return -1;
}
double dist(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(const point a,const point b)
{
int c;
double d1,d2;
c=ccw(ll,a,b);
if(c==0)
{
d1=dist(ll,a);
d2=dist(ll,b);
if(d1-d2<=-eps)
return 1;
else
return 0;
}
if(c==-1)
return 0;
return 1;
}
const int NMAX=120010;
point p[NMAX];
int h[NMAX];
int main() {
int n,i, poz, u, c;
point aux;
in>>n;
ll.x=ll.y=1000000000;
for(i=0;i<n;i++)
{
in>>p[i].x>>p[i].y;
if(p[i].y-ll.y<=-eps || (fabs(p[i].y-ll.y)<eps && p[i].x-ll.x<=-eps))
{ ll=p[i];
poz=i;}
}
aux=p[0];
p[0]=p[poz];
p[poz]=aux;
sort(p+1,p+n,cmp);
p[n]=p[0];
h[1]=0;
h[2]=1;
i=2;
u=2;
while(i<=n)
{
c=ccw(p[h[u-1]],p[h[u]],p[i]);
if(c>0)
{
h[++u]=i;
++i;
}
else
u--;
}
u--;
out<<u<<'\n';
for(i=1;i<=u;i++)
out<<setprecision(6)<<fixed<<p[h[i]].x<<" "<<p[h[i]].y<<'\n';
return 0;
}