Pagini recente » Cod sursa (job #680101) | Cod sursa (job #573534)
Cod sursa(job #573534)
#include <iostream>
#include <cstdio>
using namespace std;
const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";
const int nmax = 125000;
struct point
{
double x, y;
double panta;
}p[nmax];
int n, i, vf;
double mxx, mxy;
int maxpoint;
int st[nmax];
double calc(int i)
{
return (p[i].y - p[1].y) / (p[i].x - p[1].x);
}
struct cmp
{
bool operator()(const point &a, const point &b)const
{
if(a.panta < b.panta)
return 1;
if(a.panta == b.panta)
if(a.x < b.x)
return 1;
return 0;
}
};
double ccw(int p1, int p2, int p3)
{
return (p[p2].x - p[p1].x) * (p[p3].y - p[p1].y) - (p[p2].y - p[p1].x) * (p[p3].x - p[p1].x);
}
int main()
{
freopen(iname, "r", stdin);
freopen(oname, "w", stdout);
mxx = 2920910;
mxy = 2902902;
scanf("%d", &n);
for(i = 1; i <= n; i ++)
{
scanf("%lf %lf", &p[i].x, &p[i].y);
if(p[i].x < mxx)
{
mxx = p[i].x;
maxpoint = i;
}
if(p[i].x == mxx)
if(p[i].y < mxy)
{
mxy = p[i].y;
maxpoint = i;
}
}
swap(p[1], p[maxpoint]);
for(i = 2; i <= n; i ++)
p[i].panta = calc(i);
sort(p + 2, p + n + 1, cmp());
st[1] = 1, st[2] = 2;
vf = 2;
for(i = 3; i <= n; i ++)
{
while(vf > 2 && ccw(st[vf - 1], st[vf], i) < 0) //atentie
--vf;
st[++vf] = i;
}
printf("%d\n", vf);
for(i = 1; i <= vf; i ++)
printf("%lf %lf\n", p[st[i]].x, p[st[i]].y);
return 0;
}