Pagini recente » Cod sursa (job #1686086) | Cod sursa (job #917233)
Cod sursa(job #917233)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x,y;
bool u;
}v[120001];
int n,i,k,p,s[120001],t,j;
double eps=1e-12;
bool cmp (point A, point B)
{
if (fabs(A.y-B.y)<=eps) return (A.x<B.x);
return (A.y<B.y);
}
bool det (point A,point B,point C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-(C.x*B.y+B.x*A.y+A.x*C.y)>0;
}
int main ()
{
fin>>n;
for (i=1;i<=n;i++) fin>>v[i].x>>v[i].y;
sort (v+1,v+n+1,cmp);
k=0;p=1;
for (i=1;i>0;i=i+p)
{
if (v[i].u==1) continue;
s[++k]=i; v[i].u=1;
if (k<3) continue;
while (k>2&&det(v[s[k]],v[s[k-1]],v[s[k-2]]))
{
v[s[k-1]].u=0;
s[k-1]=s[k];
k--;
}
if (i==n) p=-1;
}
fout<<k<<"\n";
for (i=1;i<=k;i++) fout<<fixed<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
}