Cod sursa(job #1336434)

Utilizator delia_99Delia Draghici delia_99 Data 7 februarie 2015 18:35:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <algorithm>
#define NMAX 120010
#define eps 1e-12
using namespace std;
struct point
{
    double x,y;
};

point v[NMAX];
bool ok[NMAX];
int n,i,H,s[NMAX];


int cmp1(double x,double y)
{
    if(x+eps<y)  return 1;
    if(y+eps<x)  return -1;
    return 0;
}

bool cmp(point a, point b)
{
    int t;
    t=cmp1(a.x,b.x);
    if(t!=0)
    {
        if(t==1)  return true;
        else return false;
    }
    else return(cmp1(a.y,b.y)==1);

}

bool semn(point a,point b,point c)
{
    double p;
    p=a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
    return (cmp1(p,0)==1);
}

void rezolva()
{
    int q;
    sort(v+1,v+n+1,cmp);
    s[1]=1;s[2]=2;s[0]=2;
    ok[2]=true;
    i=3;
    q=1;
    while(!ok[1])
    {
        while(ok[i])
        {
            if(i==n)  q=-1;
            i+=q;

        }
        while(s[0]>=2 && !semn(v[s[s[0]]],v[s[s[0]-1]],v[i]))
        {
            ok[s[s[0]--]]=false;
        }
        s[++s[0]]=i;
        ok[s[s[0]]]=true;
    }

}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d\n",&n);
    for(i=1;i<=n;++i)
     scanf("%lf %lf\n",&v[i].x,&v[i].y);
    rezolva();
    H=s[0]-1;
    printf("%d\n",H);
    for(i=1;i<s[0];++i)
      printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
    printf("\n");
    return 0;
}