Cod sursa(job #270153)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 3 martie 2009 19:42:54
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<stdio.h>
#define N 120001
#define INF 2000000000


int u, n;
struct coord{double x, y;} a[N], q[N], aux, min;

void citire(), rezolva();

double pvect(double x1, double y1, double x2, double y2, double x3, double y3){
    return (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1);
}


int main (){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    citire();
    for ( u = 0; q[u].x != q[0].x || q[u].y != q[0].y || !u; )
        rezolva();
int i;
    printf("%d\n", u);
    for (i = 0; i < u; i++)
        printf("%.6lf %.6lf\n", q[i].x, q[i].y);
    return 0;
}


void citire(){
    scanf("%d ", &n); min.x = INF; min.y = INF;

int i;
    for (i = 1; i <= n; i++){
        scanf("%lf %lf", &a[i].x, &a[i].y);

        if (a[i].x < min.x || (a[i].x == min.x && a[i].y < min.y))
            min.x = a[i].x, min.y = a[i].y;
    }
    q[0].x = min.x; q[0].y = min.y;
}

void rezolva(){
int i;
    for (i = 2;i <= n; i++){
        if (a[i].x == q[u].x && a[i].y == q[u].y) continue;

        if (pvect(q[u].x, q[u].y, a[1].x, a[1].y, a[i].x, a[i].y)<0){
            aux = a[1];
            a[1] = a[i];
            a[i] = aux;
        }
    }
    q[++u] = a[1];
    aux = a[1]; a[1] = a[2]; a[2] = aux;
}