Pagini recente » Cod sursa (job #3002396) | Cod sursa (job #81155) | Cod sursa (job #2591725) | Cod sursa (job #2291024) | Cod sursa (job #2737255)
#include <bits/stdc++.h>
#define inf 1000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct infasuratoare
{
double x,y;
}v[120100],sol[120100];
int compare(infasuratoare A, infasuratoare B)
{
return (A.y-v[1].y)*(B.x-v[1].x) < (B.y-v[1].y)*(A.x-v[1].x);
}
int viraj_dreapta(infasuratoare A, infasuratoare B, infasuratoare C)
{
return ((A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-A.x*C.y-A.y*B.x)<0);
}
int n,i,punct,t;
double minix=inf,miniy=inf;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x<minix)
{
minix=v[i].x;
miniy=v[i].y;
punct=i;
}
else if(v[i].x==minix)
{
if(v[i].y<miniy)
{
miniy=v[i].y;
punct=i;
}
}
}
swap(v[punct],v[1]);
sort(v+2,v+n+1,compare);
t=2;
sol[1]=v[1];
sol[2]=v[2];
for(i=3;i<=n;i++)
{
while(t>2 && viraj_dreapta(sol[t-1],sol[t],v[i]))t--;
t++;sol[t]=v[i];
}
g<<t<<'\n';
for(i=1;i<=t;i++)
g<<fixed<<setprecision(12)<<sol[i].x<<" "<<fixed<<setprecision(12)<<sol[i].y<<'\n';
return 0;
}