Pagini recente » Cod sursa (job #698726) | Cod sursa (job #1060018) | Cod sursa (job #627740) | Cod sursa (job #2174170) | Cod sursa (job #2531396)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define Nmax 120001
int n, vf;
struct point
{
double x, y, a;
}p[Nmax], st[Nmax];
void load()
{
int istart;
in >> n;
p[0].x = INT_MAX;
p[0].y = INT_MAX;
for(int i = 1; i <= n; ++ i)
{
in >> p[i].x >> p[i].y;
if(p[i].y < p[0].y)
p[0] = p[i], istart = i;
else if(p[i].y == p[0].y)
if(p[i].x < p[0].x)
p[0] = p[i], istart = i;
}
swap(p[istart], p[1]);
}
void compute_angle()
{
for(int i = 1; i <= n; ++ i)
p[i].a = acos((p[i].x - p[0].x) / sqrt(pow(p[i].x - p[0].x, 2) + pow(p[i].y - p[0].y, 2)));
}
bool cmp(point c, point d)
{
return c.a < d.a;
}
double det(point p1, point p2, point p3)
{
return p1.x *(p2.y - p3.y) + p2.x *(p3.y - p1.y) + p3.x *(p1.y - p2.y);
}
void hull()
{
int i = 4;
st[++ vf] = p[1];
st[++ vf] = p[2];
st[++ vf] = p[3];
while(i <= n)
{
if(det(st[vf - 1], st[vf], p[i]) >= 0)
st[++ vf] = p[i];
else
{
do
{
-- vf;
}
while(vf >= 1 && det(st[vf - 1], st[vf], p[i]) < 0);
st[++ vf] = p[i];
}
++ i;
}
}
void output()
{
out << vf << '\n';
for(int i = 1; i <= vf; ++ i)
{
out << fixed << setprecision(6) << st[i].x;
out << ' ';
out << fixed << setprecision(6) << st[i].y;
out << '\n';
}
}
int main()
{
load();
compute_angle();
sort(p + 2, p + n + 1, cmp);
hull();
output();
return 0;
}