Cod sursa(job #270147)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 3 martie 2009 19:40:45
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 120000

using namespace std;

int n, m, u, p, ind [N];
double mx = 1000000000, my = 1000000000;
struct coord{double x, y;} a[N], q[N], aux;

void citire(), aranjare();
inline int pvect(double, double, double, double, double, double);
inline bool cmp(int j, int i){ return pvect(a[i].x, a[i].y, mx, my, a[j].x, a[j].y);}

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

	citire();
	u = 0; q[0].x = mx; q[0].y = my;
	while (q[0].x != q[u].x || q[0].y != q[u].y || !u)
		aranjare();

    printf("%d\n", u);
    for (i = 0; i < u; i++)
        printf("%lf %lf\n", q[i].x, q[i].y);

	return 0;
}


void citire(){
int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++){
		scanf("%lf %lf", &a[i].x, &a[i].y); ind[i] = i;
		if ((a[i].x < mx) || (a[i].x == mx && a[i].y < my)){
			mx = a[i].x, my = a[i].y;
			aux = a[1]; a[1] = a[i]; a[i] = aux;
		}
	}
}

void aranjare(){
    sort(ind + u + 1, ind + n +1, cmp);

	q[++u].x = mx = a[ind[u]].x;; q[u].y = my = a[ind[u]].y;
}

int 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));
}