Pagini recente » Rating Marica Sorin (Unibuc1923) | Rating Gabriel Dascalescu (Gabriel_Dascalescu) | Rating Campean Adrian (jumanji) | Cod sursa (job #2491356) | Cod sursa (job #2496645)
#include <bits/stdc++.h>
#define NMAX 120005
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n;
struct Point
{
long double x , y;
}a[NMAX];
Point s[NMAX];
long long Aria(Point a , Point b , Point c)
{
Point dif = {c.x - a.x , c.y - a.y};
a = {0 + dif.x , 0 + dif.y};
dif = {c.x - b.x , c.y - b.y};
b = {0 + dif.x , 0 + dif.y};
return a.x * b.y - b.x * b.y;
}
bool inline Custom_Compare(Point c , Point b)
{
return Aria(c , b , a[1]) < 0;
}
int main()
{
int i , top;
f >> n;
for(i = 1 ; i <= n ; i++)
{
f >> a[i].x >> a[i].y;
if(a[1].x > a[i].x)
swap(a[1] , a[i]);
else if(a[1].x == a[i].x)
if(a[1].y > a[i].y)
swap(a[1] , a[i]);
}
sort(a + 2 , a + n + 1, Custom_Compare);
s[1] = a[1];
s[2] = a[2];
top = 2;
for(i = 3 ; i <= n ; i++)
{
while(top >= 2 && Aria(a[top - 1] , a[top] , a[i]) > 0)
--top;
s[++top] = a[i];
}
g << top << '\n';
for(i = top ; i >= 1 ; i--)
g << fixed << setprecision(6) << s[i].x << ' ' << fixed << setprecision(6) << s[i].y << '\n';
return 0;
}