Cod sursa(job #1098090)

Utilizator kiralalaChitoraga Dumitru kiralala Data 4 februarie 2014 14:10:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <utility>
#define NMAX 120005
#define x first
#define y second
#define mp(x,y) make_pair(x,y)

using namespace std;

FILE* f=freopen("infasuratoare.in","r",stdin);
FILE* o=freopen("infasuratoare.out","w",stdout);

typedef pair<double,double> Point;

Point pts[NMAX],start;

int n;
int stk[NMAX],top=1;

double crossprod(Point a, Point b, Point c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool compare(Point a, Point b)
{
    return crossprod(pts[0],a,b)<0;
}

int main()
{
    scanf("%d",&n);
    start=mp(9999999999.0,9999999999.0);
    int pos;
    for(int i=0;i<n;++i)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        pts[i]=mp(x,y);
        if(pts[i]<start)
            start=pts[i],pos=i;
    }

    swap(pts[0],pts[pos]);
    sort(pts+1,pts+n,compare);

    for(int i=1;i<n;++i)
    {
        while(top-2>=0&&crossprod(pts[stk[top-2]],pts[stk[top-1]],pts[i])>0)
            top-=1;
        stk[top++]=i;
    }

    printf("%d\n",top);

    for(int i=top-1;i>=0;--i)
        printf("%.6lf %.6lf\n",pts[stk[i]].x,pts[stk[i]].y);

    return 0;
}