Pagini recente » Cod sursa (job #1411667) | Cod sursa (job #1600658) | Cod sursa (job #2900422) | Cod sursa (job #1450689) | Cod sursa (job #3216154)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct Punct {long double x , y;}a[120001] , st[120001];
int N , vf;
long double Det (Punct A , Punct B , Punct C)
{
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
long double Dist (Punct A , Punct B)
{
long double a = A.x - B.x , b = A.y - B.y;
return a * a + b * b;
}
bool fCmp (Punct A , Punct B)
{
long double d = Det ({0 , 0} , A , B);
if(d != 0)
return d > 0;
return Dist (A , {0 , 0}) > Dist (B , {0 , 0});
}
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> a[i].x >> a[i].y;
int p = 1;
for (int i = 2; i <= N; ++i)
if(a[p].y > a[i].y || (a[p].y == a[i].y && a[i].x < a[p].x))
p = i;
swap(a[1] , a[p]);
/// Sortez
sort (a + 2 , a + N + 1 , fCmp);
/// Determin punctele coliniare cu originea si cu a[2]
// int poz = 3;
// while(poz <= N && Det (a[1] , a[2] , a[poz]) == 0)
// ++poz;
// --poz;
/// Simetrizez secventa
// for(int i = 2 , j = poz; i < j; ++i , --j)
// swap(a[i] , a[j]);
/// Realiz. infasuratoarea
st[++vf] = a[1] , st[++vf] = a[2];
for (int i = 3; i <= N; ++i)
{
while(vf >= 2 && Det (st[vf - 1] , st[vf] , a[i]) < 0)
--vf;
st[++vf] = a[i];
}
/// Afisez infas.
fout << vf << "\n";
fout << fixed << setprecision(12);
for (int i = 1; i <= vf; ++i)
fout << st[i].x << " " << st[i].y << "\n";
}