Pagini recente » Cod sursa (job #2788011) | Cod sursa (job #1131173) | Cod sursa (job #251455) | Cod sursa (job #3188615) | Cod sursa (job #2661595)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct
{
double x,y,unghi;
} stiva[120005],v[120005],Pct;
int n,h;
double Dreapta(Punct a,Punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool Compare(const Punct &a,const Punct &b)
{
if(a.unghi==b.unghi)
{
if(a.unghi<=3.1415/2)
return a.x>b.x;
else return a.x<b.x;
}
return a.unghi<b.unghi;
}
long long int Determinant(Punct a,Punct b,Punct 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;
}
int main()
{
f>>n;
Pct.x=1e9+1;
Pct.y=1e9+1;
for(int i=1; i<=n; i++)
{
f>>v[i].x>>v[i].y;
if((Pct.y>v[i].y)||(Pct.y==v[i].y&&Pct.x>v[i].x))
Pct=v[i];
}
for(int i=1; i<=n; i++)
v[i].unghi=acos((v[i].x-Pct.x)/Dreapta(Pct,v[i]));
sort(v+1,v+n+1,Compare);
for(int i=1; i<=n; i++)
{
stiva[++h]=v[i];
while(h>3&&Determinant(stiva[h-2],stiva[h-1],stiva[h])<=0)
stiva[h-1]=stiva[h],h--;
}
g<<h<<'\n';
for(int i=1;i<=h;i++)
g<<fixed<<setprecision(6)<<stiva[i].x<<' '<<stiva[i].y<<'\n';
return 0;
}