Cod sursa(job #363703)

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

using namespace std;

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

int ind[N],S[N];
double 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(double x1, double y1, double x2, double y2, double x3, double 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("%lf%lf",&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;
	}
    double 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);

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

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

    B[n].x=0; B[n].y=0;
    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("%lf %lf\n",B[S[i]].x-plx,B[S[i]].y-ply);

	return 0;
}