Pagini recente » Cod sursa (job #900263) | Cod sursa (job #1907456) | Cod sursa (job #1918525) | Cod sursa (job #3238239) | Cod sursa (job #2753933)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iostream>
const double eps = 1.0e-14;
const int NMAX = 10000;
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<<P[h[i]].x<<" "<<P[h[i]].y<<"\n";
}
}