Pagini recente » Cod sursa (job #1672012) | Cod sursa (job #404917) | Cod sursa (job #2894015) | Cod sursa (job #1668720) | Cod sursa (job #2768390)
#include <bits/stdc++.h>
#define NMAX 120005
#define ld long double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct elem
{
ld x, y;
}points[NMAX], s[NMAX];
ld det(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3)
{
return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}
ld distance(ld x1, ld y1, ld x2, ld y2)
{
return (x2 - x1) * (x2 - x1) - (y2 - y1) * (y2 - y1);
}
bool cmp(elem a, elem b)
{
ld d = det(0, 0, a.x, a.y, b.x, b.y);
if(d == 0)
{
int d1 = distance(0, 0, a.x, a.y);
int d2 = distance(0, 0, b.x, b.y);
return d1 > d2;
}
return d > 0;
}
int main()
{
f >> n;
for(int i = 1; i <= n; i++)
f >> points[i].x >> points[i].y;
int mini = 1;
for(int i = 2; i <= n; i++)
if(points[i].y < points[mini].y || (points[i].y == points[mini].y && points[i].x < points[mini].x) )
mini = i;
points[0] = points[mini];
swap(points[1], points[mini]);
for(int i = 1; i <= n; i++)
points[i].x -= points[0].x, points[i].y -= points[0].y;
sort(points + 2, points + 1 + n, cmp);
int i;
for(i = 3; i <= n; i++)
if(det(points[1].x, points[1].y, points[2].x, points[2].y, points[i].x, points[i].y))
break;
int j = 2;
i--;
while(i > j)
{
swap(points[i], points[j]);
i--, j++;
}
s[1] = points[1];
s[2] = points[2];
int k = 2;
for(int i = 3; i <= n; i++)
{
while(k >= 2 && det(s[k - 1].x, s[k - 1].y, s[k].x, s[k].y, points[i].x, points[i].y) <= 0)
k--;
s[++k] = points[i];
}
g << k << "\n";
for(int i = 1; i <= k; i++)
g << setprecision(12) << fixed << s[i].x + points[0].x << " " << s[i].y + points[0].y << "\n";
return 0;
}