Cod sursa(job #1163711)

Utilizator Barcau_EmanuelBarcau Emanuel Barcau_Emanuel Data 1 aprilie 2014 16:23:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 120010
#define INF 1<<30
using namespace std;
 
int i,n,k,s[Nmax],poz;
 
struct punct
{
    double x,y,tg;
} v[Nmax],o,aux;
 
int cmp ( punct a, punct b)
{
    if(a.tg==b.tg) return a.x<b.x;
 
    return a.tg<b.tg;
}
 
int convex()
{
    punct a,b,c;
    double S;
 
    a=v[s[k-1]];
    b=v[s[k]];
    c=v[i];
 
    S=(a.x-c.x)*(b.y-a.y)+(a.x-b.x)*(a.y-c.y);
 
    if(S>0) return 1;
    return 0;
}
 
 
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
 
    scanf("%d",&n);
 
    o.x=o.y=INF;
 
    for(i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
 
        if(v[i].x < o.x || v[i].x == o.x && v[i].y < o.y)
            o=v[i],poz=i;
    }
 
    aux=v[1]; v[1]=v[poz]; v[poz]=aux;
 
    for(i=2;i<=n;i++)
        v[i].tg= ( v[i].y - o.y ) / (v[i].x - o.x);
 
    sort(v+2,v+n+1,cmp);
 
    s[1]=1; s[2]=2; k=2;
 
    for(i=3;i<=n;i++)
    {
        while ( !convex() && k>2 ) k--;
        s[++k]=i;
    }
 
    printf("%d\n",k);
 
    for(i=1;i<=k;i++)
        printf("%0.6lf %0.6lf\n",v[s[i]].x,v[s[i]].y);
    return 0;
}