Pagini recente » Istoria paginii utilizator/gheorghe_oana_maria_325ca | Cod sursa (job #2037868) | Cod sursa (job #358631) | Cod sursa (job #2335814) | Cod sursa (job #2019670)
#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);
}
int ccw(point a, point b, point c)
{
int cc = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if(cc == 0) return 0;
if(cc < 0) return -1;
if(cc > 0) return 1;
}
int cmp(point A, point B)
{
double d1, d2;
int c = ccw(LL, A, B);
if(c == 0)
{
d1 = dist(LL, A);
d2 = dist(LL, B);
if(d1 - d2 >= eps) return 0;
return 1;
}
return c == 1;
}
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;
}