Pagini recente » Cod sursa (job #987017) | Cod sursa (job #1977926) | Cod sursa (job #1865166) | Cod sursa (job #1263786) | Cod sursa (job #2376172)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
//ofstream fout ("infasuratoare.out");
#define x first
#define y second
const int NMAX = 120005;
pair <double, double> v[NMAX];
int n, top, st[NMAX];
double det (pair <double, double> A, pair <double, double> B, pair <double, double> C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp (pair <double, double> A, pair <double, double> B)
{
return det(v[1], A, B) < 0;
}
int main()
{
freopen("infasuratoare.out","w",stdout);
fin >> n;
for (int i=1; i<=n; i++)
{
fin >> v[i].x >> v[i].y;
if (i > 1 && v[i] < v[1]) swap(v[1], v[i]);
}
sort(v+2,v+n+1,cmp);
// for (int i=1; i<=n; i++)
//cout << v[i].x << " " << v[i].y << "\n";
st[1] = 1;
st[2] = 2;
top = 2;
for (int i=3; i<=n; i++)
{
while (top >= 2 && det(v[st[top-1]], v[st[top]], v[i]) > 0) --top;
st[++top] = i;
}
printf("%d \n", top);
for (int i=top; i>=1; i--)
printf("%.12f %.12f\n",v[st[i]].x,v[st[i]].y);
return 0;
}