Pagini recente » Cod sursa (job #1939151) | Cod sursa (job #2983666) | Cod sursa (job #2662087) | Cod sursa (job #2558698) | Cod sursa (job #2602192)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define INF 0x3f3f3f3f
struct punct
{
double x,y;
}P[120005],stiva[120005],minim;
double determinant (punct A,punct B,punct C)
{
A.x-=B.x;
A.y-=B.y;
C.x-=B.x;
C.y-=B.y;
double produs=A.x*C.y-A.y*C.x;
return produs;
}
bool cmp (punct A,punct B)
{
return (determinant(P[1],A,B)<0);
}
int N;
int main()
{
fin >> N;
minim.x=minim.y=INF;
int start;
int i;
for (i=1;i<=N;++i)
{
fin >> P[i].x >> P[i].y;
if (P[i].x<minim.x)
{
minim=P[i];
start=i;
}
else if (P[i].x==minim.x && P[i].y<minim.y)
{
minim.y=P[i].y;
start=i;
}
}
punct aux=P[1];
P[1]=P[start];
P[start]=aux;
sort(P+2,P+N+1,cmp);
stiva[1]=P[1];
stiva[2]=P[2];
int M=2;
for (i=3;i<=N;++i)
{
while (M>=2 && determinant(stiva[M-1],stiva[M],P[i])>0)
{
--M;
}
++M;
stiva[M]=P[i];
}
fout << M << '\n';
for (i=M;i>=1;--i)
{
fout << setprecision(12) << fixed << stiva[i].x << " " << stiva[i].y << '\n';
}
fin.close();
fout.close();
return 0;
}