Pagini recente » Cod sursa (job #1111380) | Cod sursa (job #2904122) | Cod sursa (job #1630060) | Cod sursa (job #580965) | Cod sursa (job #2989289)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x, y;
};
const int NMAX = 120005;
int n;
int idx[NMAX];
point arr[NMAX];
inline double det(point a, point b, point c)
{
return (a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y);
}
inline bool Trig(const point &a, const point &b)
{
return det(arr[1], a, b) > 0;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++ i)
fin >> arr[i].x >> arr[i].y;
int minY = arr[1].y, minpos = 1;
for(int i = 1; i <= n; ++ i)
{
if(minY > arr[i].y)
{
minpos = i;
minY = arr[i].y;
}
}
swap(arr[1], arr[minpos]);
sort(arr + 2, arr + n + 2, Trig);
idx[1] = 1;
idx[2] = 2;
int k = 2;
for(int i = 3; i <= n; ++i)
{
while(k > 1 && det(arr[idx[k-1]], arr[idx[k]], arr[i]) <= 0)
k--;
idx[++k] = i;
}
fout << k << '\n';
for(int i = 1; i <= k; ++ i)
fout << fixed << setprecision(12) << arr[idx[i]].x << ' ' << arr[idx[i]].y << '\n';
}