Pagini recente » Cod sursa (job #2775211) | Cod sursa (job #2946574) | Cod sursa (job #192657) | Cod sursa (job #1750824) | Cod sursa (job #3215096)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct Punct
{
double l , c;
double up;
}a[120001] , st[120001];
int N , k;
double Dist (Punct a , Punct b)
{
int x = a.l - b.c , y = a.c - b.c;
return sqrt (x * x + y * y);
}
bool fCmp (Punct A , Punct B)
{
if(A.up != B.up)
return A.up < B.up;
else
{
if(A.c != B.c)
return A.c < B.c;
return A.l < B.l;
}
}
int Det (Punct A , Punct B , Punct C)
{
return A.l * (B.c - C.c) + B.l * (C.c - A.c) + C.l * (A.c - B.c);
}
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> a[i].l >> a[i].c;
int p = 1;
for (int i = 2; i <= N; ++i)
if(a[i].c < a[p].c || (a[i].c == a[p].c && a[i].l < a[p].l))
p = i;
swap(a[p] , a[1]);
for (int i = 2; i <= N; ++i)
a[i].up = acos(1.0 * (a[i].l - a[1].l) / Dist (a[i] , a[1]));
sort (a + 2 , a + N + 1 , fCmp);
st[++k] = a[1];
st[++k] = a[2];
for (int i = 3; i <= N; ++i)
{
while(k >= 2 && Det (a[i] , st[k] , st[k - 1]) > 0)
--k;
st[++k] = a[i];
}
fout << k << "\n";
for (int i = 1; i <= k; ++i)
fout << fixed << setprecision(12) << st[i].l << " " << st[i].c << "\n";
}