Cod sursa(job #261057)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 17 februarie 2009 20:46:53
Problema Infasuratoare convexa Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<string.h>

int n, m, mx = 2000, my = 2000, u, p, radical[2000];
long plibera;
double arie;


struct coord{double x, y;} a[120], q[120], aux;

void citire(), aranjare();
int pvect(double, double, double, double, double, double);

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

    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[1].x; my = a[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;
}