Cod sursa(job #270315)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 3 martie 2009 21:31:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<stdio.h>
#include<algorithm>

using namespace std;
#define N 120001
#define INF 2000000000


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

void citire(), rezolva();

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

inline bool cmp(int j, int i){ return pvect(a[i].x, a[i].y, mi.x, mi.y, a[j].x, a[j].y);}

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

    citire();
int i;
    u = 2;
    for (i = 2; i <= n; i++){
        while (!pvect(q[u-2].x, q[u-2].y, q[u-1].x, q[u-1].y, a[ind[i]].x, a[ind[i]].y)) u--;
        q[u++] = a[ind[i]];
    }
    printf("%d\n", u-1);
    for (i = 0 ; i < u-1; i++ )
        printf("%.6lf %.6lf\n", q[i].x, q[i].y);

    return 0;
}


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

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

        if (a[i].x < mi.x || (a[i].x == mi.x && a[i].y < mi.y))
            mi.x = a[i].x, mi.y = a[i].y, ct = i;
    }
    aux = a[ct]; a[ct] = a[n]; a[n] = aux;

    q[0] = mi;

    sort(ind + 1, ind + n, cmp);

    q[1] = a[ind[1]];
}