Pagini recente » Cod sursa (job #1362765) | Cod sursa (job #723852) | Cod sursa (job #2296794) | Cod sursa (job #2660566) | Cod sursa (job #1921015)
#include<bits/stdc++.h>
using namespace std;
int n, st = 2;
struct dot{double x,y;};
dot A[120100], sta[120100];
double f(dot a, dot b, dot c)
{
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
bool comp(dot a, dot b)
{
return (f(A[1],a,b) < 0);
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
int poz = 1;
for(int i = 1; i <= n; i++)
{
cin >> A[i].x >> A[i].y;
if (A[i].x < A[poz].x || (A[i].x == A[poz].x && A[i].y < A[poz].y)) poz = i;
}
swap(A[1], A[poz]);
sort(A+2,A+n+1, comp);
sta[1] = A[1]; sta[2] = A[2];
for (int i = 3; i <= n; i++)
{
while(st >= 2 && f(sta[st-1],sta[st],A[i]) > 0) st--;
st++;
sta[st] = A[i];
}
cout << st << "\n";
while(st)
{
cout<< setprecision(13) << fixed << sta[st].x << " " << sta[st].y << "\n";
st--;
}
}