Cod sursa(job #261079)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 17 februarie 2009 21:02:08
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

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

void citire(), aranjare();
int pvect(double, double, double, double, double, double);
bool cmp(int j, int i){ return (pvect(a[i].x, a[i].y, mx, my, a[j].x, a[j].y) >= 0);}
inline int modul(int a){
	if (a > 0) return a;else return -a;
}

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(){
int i, j;
    sort(ind + 1, ind + n + 1, cmp);
/*    for (i = 1; i <= n-1; i++)
        for (j = i+1; j <=n; j++)
            if (pvect(a[i].x, a[i].y, mx, my, a[j].x, a[j].y) >= 0){
                aux = a[i]; a[i] = a[j]; a[j] = aux;
            }
*/
	mx = a[ind[1]].x; my = a[ind[1]].y;

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

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