Pagini recente » Cod sursa (job #1913496) | Cod sursa (job #705127) | Cod sursa (job #681605) | Cod sursa (job #1476317) | Cod sursa (job #2281903)
#include <fstream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, poz;
double auxx, auxy;
struct punct{double x, y;}A[120005], P0, s[120005];
double cp(punct A, punct B, punct P0)
{
return (A.x-P0.x)*(B.y-P0.y)-(B.x-P0.x)*(A.y-P0.y);
}
bool comp(punct A, punct B)
{
if(cp(A, B, P0)>0) return 1;
if(cp(A, B, P0)<0) return 0;
if(A.x*A.x+A.y*A.y < B.x*B.x+B.y*B.y) return 1;
return 0;
}
int main()
{
fin>>n;
fin>>P0.x>>P0.y;
A[1].x=P0.x, A[1].y=P0.y;
for(int i=2;i<=n;++i)
{
fin>>A[i].x>>A[i].y;
if(A[i].x<P0.x)
{
P0.x=A[i].x;
P0.y=A[i].y;
poz=i;
}
else
{
if(A[i].x==P0.x && A[i].y<P0.y)
{
P0.x=A[i].x;
P0.y=A[i].y;
poz=i;
}
}
}
//fout<<P0.x<<' '<<P0.y;
swap(A[1], A[poz]);
sort(A+2, A+n+1, comp);
s[1]=A[1];
s[2]=A[2];
int vf1=2, vf2=1, nr=2;
int i=3;
while(nr>=2)
{
if(cp(s[vf2], s[vf1], A[i])>0)
{
if(i==n+1)
{break;}
else
{
s[++nr]=A[i];
++vf1;
++vf2;
++i;
}
}
else
{
s[nr].x=0;
s[nr].y=0;
--nr;
--vf1;
--vf2;
}
}
fout<<nr<<'\n';
for(int i=2;i<=nr;++i)
fout<<setprecision(12)<<fixed<<s[i].x<<' '<<s[i].y<<'\n';
fout<<s[1].x<<' '<<s[1].y;
return 0;
}