Pagini recente » Cod sursa (job #828158) | ichc_preoji2010 | Cod sursa (job #2221080) | Cod sursa (job #3194853) | Cod sursa (job #2144289)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMax = 120005;
struct Punct
{
double x, y;
}v[NMax];
int N;
void Read()
{
scanf("%d", &N);
scanf("%lf %lf", &v[1].x, &v[1].y);
for(int i=2; i<=N; ++i)
{
scanf("%lf %lf", &v[i].x, &v[i].y);
if(v[i].y < v[1].y)
{
swap(v[i],v[1]);
}
else
if(v[i].y==v[1].y && v[i].x < v[1].x)
swap(v[1], v[i]);
}
}
double UnghiPolar(Punct a, Punct b, Punct c)
{
return (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
}
struct Operator{
bool operator()(Punct a, Punct b)
{
if(UnghiPolar(v[1],a,b) >= 0)
return true;
return false;
}
} cmp;
Punct st[NMax];
int vf = 0;
void Graham()
{
st[++vf] = v[1];
st[++vf] = v[2];
st[++vf] = v[3];
for(int i=4; i<=N; ++i)
{
while(vf>=2 && UnghiPolar(st[vf-1], st[vf], v[i]) > 0);
--vf;
st[++vf] = v[i];
}
cout << vf << "\n";
for(int i=1; i<=vf; ++i)
cout << st[i].x << " " << st[i].y << "\n";
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
Read();
sort(v+2, v+N+1, cmp);
Graham();
return 0;
}