Pagini recente » Cod sursa (job #2158015) | Cod sursa (job #29731) | Cod sursa (job #698703) | Cod sursa (job #2097574) | Cod sursa (job #2753942)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
const double eps = 1.0e-14;
const int NMAX = 120000;
struct POINT
{
double x, y;
};
double cp (const POINT& p1, const POINT& p2, const POINT& p3)
{
return ((p2.x - p1.x) * (p3.y-p2.y) - (p2.y-p1.y) * (p3.x-p2.x));
}
int ccw (const POINT& p1, const POINT& p2, const POINT& p3)
{
/// 1 ccw 0 coliniar -1 cw
double c = cp (p1, p2, p3);
if (fabs(c) < eps)
return 0;
if (c >= eps)
return 1;
return -1;
}
POINT P[NMAX+5];
POINT LL;
int h[NMAX+5];
bool cmp (POINT p1, POINT p2)
{
return (ccw(LL, p1, p2) > 0);
}
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int main ()
{
int n,i,top;
fin>>n;
fin>>P[0].x>>P[0].y;
for(i=1;i<n;i++)
{
fin>>P[i].x>>P[i].y;
if(P[i].y - P[0].y<=-eps || (fabs(P[i].y-P[0].y)<eps && P[i].x - P[0].x<=-eps))
swap (P[0],P[i]);
}
LL=P[0];
sort (P+1,P+n, cmp);
h[0]=0;
h[1]=1;
top=1;
P[n]=P[0];
i=2;
while(i<=n)
{
if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
{
h[++top]=i;
i++;
}
else
top--;
}
//for(i=0;i<top;i++)
// fout<<h[i]<<" ";
//fout<<"\n";
fout << top << "\n";
for (i=0; i<top; i++)
fout << fixed << setprecision(6) << P[h[i]].x << " " << P[h[i]].y << "\n";
}