Pagini recente » Cod sursa (job #905479) | Cod sursa (job #1960690) | Cod sursa (job #2652383) | Cod sursa (job #432102) | Cod sursa (job #3141865)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double K,L,ans=1e9;
struct point
{
double x,y;
} v[200005],start;
vector<point> hull;
double aria(point a,point b,point c)
{
a.x-=c.x;
a.y-=c.y;
b.x-=c.x;
a.y-=c.y;
return (a.x*b.y-a.y*b.x);
}
bool comp(point a,point b)
{
if(a.x==start.x&&a.y==start.y)
return 1;
if(b.x==start.x&&b.y==start.y)
return 0;
double ar=aria(start,a,b);
if(ar!=0)
return ar<0;
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
double dist(point A,point B)
{
return sqrt(1.0L*((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)));
}
double unghi(point B,point A,point C)
{
double a=dist(B,C);
double b=dist(A,C);
double c=dist(A,B);
double u=(b*b+c*c-a*a)/(2.0*b*c);
u=acos(u);
return u;
}
void check(double xx, double yy)
{
point p={xx,yy};
if(xx<-L||xx>L||yy<-L||yy>L)
return;
double maxim=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
double u=unghi(v[i],p,v[j]);
maxim=max(maxim,u);
}
ans=min(ans,maxim);
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fin>>n;
if(n==1)
{
fout<<0;
return 0;
}
for(int i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(i==1)
start=v[i];
if(v[i].x<start.x)
start=v[i];
else if(v[i].x==start.x&&v[i].y<start.y)
start=v[i];
}
sort(v+1,v+n+1,comp);
for(int i=1;i<=n;i++)
{
while(hull.size()>=2)
{
int lg=hull.size();
double ar=aria(hull[lg-2],hull[lg-1],v[i]);
if(ar>0)
hull.pop_back();
else
break;
}
hull.push_back(v[i]);
}
fout<<hull.size()<<'\n';
for(auto i:hull)
fout<<fixed<<setprecision(12)<<i.x<<' '<<i.y<<'\n';
return 0;
}