Pagini recente » Cod sursa (job #3197657) | Cod sursa (job #2423878) | Cod sursa (job #422226) | Cod sursa (job #2858603) | Cod sursa (job #2575299)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
long double cx=INT_MAX,cy=INT_MAX;
struct punct
{
long double x,y;
}v[120100],st[120100];
int compare(punct A,punct B)
{
return (atan2(A.x-cx,A.y-cy) > atan2(B.x-cx,B.y-cy));
}
int semn(long double val)
{
if(val==0)return 0;
else if(val>0)return -1;
else return 1;
}
int viraj_dreapta(punct A,punct B,punct C)
{
return (semn(A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - A.x*C.y - A.y*B.x));
}
int n,poz,i,t;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x<cx)
{
cx=v[i].x;
cy=v[i].y;
poz=i;
}
else if(v[i].x==cx)
{
if(v[i].y<cy)
{
cy=v[i].y;
poz=i;
}
}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,compare);
t=2;
st[1]=v[1];
st[2]=v[2];
for(i=3;i<=n;i++)
{
while(t>2 && viraj_dreapta(st[t-1],st[t],v[i])==1)t--;
t++;
st[t]=v[i];
}
g<<t<<'\n';
for(i=1;i<=t;i++)
{
g<<fixed<<setprecision(12)<<st[i].x<<" " <<fixed<<setprecision(12)<<st[i].y<<'\n';
}
return 0;
}