Pagini recente » Cod sursa (job #1677868) | Cod sursa (job #375158) | Cod sursa (job #1858140) | Cod sursa (job #2203368) | Cod sursa (job #1879990)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 120001
#define point pair < double , double >
#define x first
#define y second
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, i , index;
vector < point > v;
point mx;
vector < point > st;
double det ( point a , point b , point c)
{
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) ;
}
bool cmp ( point a , point b )
{
return det(v[1],a,b) < 0;
}
int main()
{
f >> n;
v = vector < point > (n+1);
f >> v[1].x >> v[1].second;
mx = v[1];
for ( i = 2; i <= n ; i++ )
{
f >> v[i].x >> v[i].second;
if ( mx.x > v[i].x or ( mx.x == v[i].x and mx.y > v[i].y) )
{
mx = v[i];
index = i;
}
}
swap(v[1],v[index]);
sort(v.begin()+2,v.end(),cmp);
st = vector < point > (n+1);
st[1] = v[1];
st[2] = v[2];
int varf = 2;
for ( i = 3; i <= n ; i++ )
{
while ( varf >= 2 and (det(v[i],st[varf-1],st[varf]) > 0) ) varf--;
st[++varf] = v[i];
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n",varf);
while ( varf )
{
printf("%.12f %.12f\n" ,st[varf].x , st[varf].y);
varf--;
}
return 0;
}