Pagini recente » Cod sursa (job #453377) | Cod sursa (job #1155433) | Cod sursa (job #2277787) | Cod sursa (job #2108510) | Cod sursa (job #2949692)
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
const int dim = 12e4 + 5;
struct coord
{
double lin , col;
}v[dim];
int st[dim];
double Coliniaritate (coord a , coord b , coord c)
{
return (b.lin - a.lin) * (c.col -a.col) - (b.col - a.col) * (c.lin - a.lin);
}
bool cmp (coord a , coord b)
{
return (Coliniaritate(v[1] , a , b) < 0);
}
int main()
{
int n;
cin >> n;
int p = 1 ;
for(int i = 1 ; i <= n ; ++i)
cin >> v[i].lin >> v[i].col;
for(int i = 2 ; i <= n ; ++i)
if(v[i].lin < v[p].lin || (v[i].lin == v[p].lin && v[i].col < v[p].col))
p = i;
swap(v[1] , v[p]);
sort(v+2 , v+n+1 , cmp);
int k = 0;
st[++k] = 1 , st[++k] = 2;
for(int i = 3 ; i <= n ; ++i)
{
while(k > 3 && Coliniaritate(v[st[k-1]] , v[st[k]] , v[i]) > 0)
--k;
st[++k] = i;
}
cout << k << '\n';
cout << fixed << setprecision(12);
for(int i = k ; i >= 1 ; --i)
cout << v[st[i]].lin << ' ' << v[st[i]].col << '\n';
}