Cod sursa(job #411107)

Utilizator cristikIvan Cristian cristik Data 4 martie 2010 18:44:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
#include <algorithm>
#define maxn 130000
using namespace std;
struct punct
{
    double x,y;
};
punct p[maxn];
int n,i,k,top,stack[maxn];
void swap(int i,int j)
{
    punct aux=p[i]; p[i]=p[j]; p[j]=aux;
}
int cmp(punct a,punct b)
{
    return(double)(a.x-p[1].x)*(b.y-p[1].y)>(double)(b.x-p[1].x)*(a.y-p[1].y);
}
int sign(int i,int j,int k)
{
    double x1,y1;
    x1=(p[i].x-p[k].x)*(p[j].y-p[k].y);
    y1=(p[j].x-p[k].x)*(p[i].y-p[k].y);
    if(x1-y1>0) return 1;
    return -1;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1,k=1; i<=n; i++)
    {
        scanf("%lf %lf",&p[i].x,&p[i].y);
        if(p[i].x<p[k].x) k=i;
        if(p[i].x==p[k].x && p[i].y<p[k].y) k=i;
    }
    swap(1,k);
    sort(p+2,p+n+1,cmp);
    stack[++top]=1;
    for(i=2; i<=n; i++)
    {
        while(top>=2 && sign(stack[top-1],stack[top],i)<0) --top;
        stack[++top]=i;
    }
    printf("%d\n",top);
    for(i=1; i<=top; i++)
     printf("%lf %lf\n",p[stack[i]].x,p[stack[i]].y);
    return 0;
}