Pagini recente » Cod sursa (job #1575488) | Cod sursa (job #2783001) | Cod sursa (job #2885693) | Cod sursa (job #2004658) | Cod sursa (job #2019673)
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <cstdio>
using namespace std;
const double EPS = 10e-12;
struct point
{
double x, y;
};
point LL;
double dist(point a, point b)
{
double dx = a.x-b.x, dy = a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
bool equal(double a, double b)
{
return fabs(a - b) < EPS;
}
double crossProduct(point p1, point p2, point p3)
{
return (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x);
}
int ccw(point p1, point p2, point p3)
{
double cp = crossProduct(p1, p2, p3);
if(equal(cp, 0.0))
return 0;
if(cp < 0) return -1;
return 1;
}
bool cmp(point p1, point p2)
{
double cw = ccw(LL, p1, p2);
if(cw == 1) return 1;
else if(cw == -1) return 0;
else
{
if(dist(LL, p1) < dist(LL, p2)) return 1;
else return 0;
}
}
ifstream fin("infasuratoare.in");
int main()
{
freopen("infasuratoare.out", "w", stdout);
int n;
fin >> n;
point p[n+2];
for(int i = 1; i <= n; i++)
{
fin >> p[i].x >> p[i].y;
}
int ll = 1;
for(int i = 2; i <= n; i++)
if(p[i].y < p[ll].y || (p[i].y == p[ll].y && p[i].x < p[ll].x))
ll = i;
p[0] = p[ll];
LL = p[ll];
p[ll] = p[n];
sort(p+1, p+n, cmp);
p[n] = p[0];
int h[n+1];
h[0] = 0;
h[1] = 1;
int top = 1;
int i = 2;
while(i <= n)
{
if(ccw(p[h[top-1]], p[h[top]], p[i]) >= 0)
{
top++;
h[top] = i;
i++;
}else top--;
}
i = n-1;
while(ccw(LL, p[i-1], p[i]) == 0)
{
h[top++] = i-1;
i--;
}
printf("%d\n", top);
for(int i = 0; i < top; i++)
{
printf("%.6f %.6f\n", p[h[i]].x, p[h[i]].y);
}
return 0;
}