Cod sursa(job #781775)

Utilizator my666013Test Here my666013 Data 25 august 2012 00:20:02
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Max 120001

struct point{ double x,y; }s[Max],s1[Max],s2[Max];
int n,n1,n2;

bool sort_type(point a,point b){ return a.x < b.x; }

double delta(point a,point b,point c){
    return a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y
        - a.x * c.y;
}

void subsets(){
    s1[0] = s2[0] = s[0];
    n1 = n2 = 1;
    for(int i=1;i<n-1;i++)
    if( delta(s[0],s[n-1],s[i]) > 0 )
        s1[n1++] = s[i]; else
        s2[n2++] = s[i];
    s1[n1++] = s2[n2++] = s[n-1];
}

void up_subset(){
    int n = 2;
    for(int i=2;i<n1;i++)
    {
        while(n >= 2 && delta(s1[n-2],s1[i],s1[n-1]) < 0)n--;
        s1[n++] = s1[i];
    }
    n1 = n;
}

void down_subset(){
    int n = 2;
    for(int i=2;i<n2;i++)
    {
        while(n >= 2 && delta(s2[n-2],s2[i],s2[n-1]) > 0)n--;
        s2[n++] = s2[i];
    }
    n2 = n;
}

int main(){

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%lf %lf",&s[i].x,&s[i].y);

    sort(s,s+n,sort_type);
    subsets();
    up_subset();
    down_subset();

    printf("%d\n",n1+n2-2);
    for(int i=n1-1;i>=0;i--)printf("%lf %lf\n",s1[i].x,s1[i].y);
    for(int i=1;i<n2-1;i++)printf("%lf %lf\n",s2[i].x,s2[i].y);

  //  for(int i=0;i<n2;i++)printf("%lf %lf\n",s2[i].x,s2[i].y);

    return 0;
}