Pagini recente » Cod sursa (job #847723) | Cod sursa (job #1936184) | Cod sursa (job #245593) | Cod sursa (job #2747563) | Cod sursa (job #1650432)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double inf=1000000003;
struct pct
{ double x,y; } p[120005],a[120005];
int n,k;
double px=inf,py;
double cross(pct a,pct b,pct c)
{
return (double) 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 panta(pct a)
{ return (double) (a.y-py)/(a.x-px); }
bool comp(pct a,pct b)
{ double e1=(double) (a.y-py)/(a.x-px), e2=(double) (b.y-py)/(b.x-px);
if (a.y==py && a.x==px) return 1;
if (b.y==py && b.x==px) return 0;
return e1>e2;
}
int main()
{ int i,j;
f>>n;
for(i=1;i<=n;i++)
{f>>p[i].x>>p[i].y;
if (p[i].x<px || (p[i].x==px && p[i].y<py))
{px=p[i].x; py=p[i].y;}
}
sort(p+1,p+n+1,comp);
k=3; a[1]=p[1]; a[2]=p[2]; a[3]=p[3];
for(i=4;i<=n;i++)
{ //cout<<p[i].x<<" "<<p[i].y<<"\n";
if (i==4)
{
//cout<<cross(a[2],a[3],p[i]);
}
while(k>=3 && cross(a[k-1],a[k],p[i])>=0)
k--;
k++; a[k]=p[i];
}
g<<k<<"\n";
for(i=1;i<=k;i++)
g<<fixed<<setprecision(12)<<a[i].x<<" "<<a[i].y<<"\n";
return 0;
}