Cod sursa(job #363695)

Utilizator RobybrasovRobert Hangu Robybrasov Data 14 noiembrie 2009 11:13:21
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define inf 0x3f3f3f3f
#define N 120005

using namespace std;

struct coord
{
    float x,y;
} A[N],B[N];

int ind[N],S[N];
float panta[N];

bool cmp(int i, int j)
{
    if (panta[i]==panta[j])
    {
        if (A[i].x==0) return fabs(A[i].y)>fabs(A[j].y);
        return fabs(A[i].x)>fabs(A[j].x);
    }
    return panta[i]<panta[j];
}

int det(float x1, float y1, float x2, float y2, float x3, float y3)
{
    return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)>=0;
}

int main()
{
    int n,i,pmin=1;
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
	{
	    scanf("%f%f",&A[i].x,&A[i].y);
	    if (A[i].x<A[pmin].x || (A[i].x==A[pmin].x && A[i].y<A[pmin].y)) pmin=i;
	    ind[i]=i;
	}
    float plx=-A[pmin].x, ply=-A[pmin].y;

    for (i=1; i<=n; i++) A[i].x+=plx, A[i].y+=ply;
    for (i=1; i<=n; i++)
    {
        if (A[i].x==0)
        {
            if (A[i].y<0) panta[i]=-inf;
            else panta[i]=inf;
        }
        else panta[i]=A[i].y/A[i].x;
    }

    sort(ind+1,ind+n+1,cmp);

    B[1].x=0; B[1].y=0;
    for (i=1; A[ind[i]].x || A[ind[i]].y; i++)
        B[i+1]=A[ind[i]];

    for (i++; A[ind[i]].x || A[ind[i]].y; i++)
        B[i]=A[ind[i]];

    S[1]=1; S[2]=2;
    int p=2;
    for (i=3; i<=n; i++)
    {
        while (p>1 && !det(B[S[p-1]].x,B[S[p-1]].y,B[S[p]].x,B[S[p]].y,B[i].x,B[i].y)) p--;
        S[++p]=i;
    }
    printf("%d\n",p);
    for (i=1; i<=p; i++) printf("%f %f\n",B[S[i]].x-plx,B[S[i]].y-ply);

	return 0;
}