Cod sursa(job #1110538)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 18 februarie 2014 10:21:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <iomanip>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double,double> point;

FILE *f = fopen("infasuratoare.in","r");
FILE *g = fopen("infasuratoare.out","w");

int n, i, p;

point v[120005], tmp;

int det(const point &a, const point &b, const point &c) {
	if( (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) > 0)
		return -1;
	else
		return 1;
}

bool cmp(const point &a, const point &b) {
	if(det(v[1],a,b)==-1)
		return 1;
	return 0;
}

int main() {
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
	p=1;
	for(i=2;i<=n;i++)
		if(v[i].y<v[p].y || (v[i].x==v[p].x && v[i].x<v[p].x) )
			p=i;
	tmp=v[p];
	v[p]=v[1];
	v[1]=tmp;
	sort(v+2,v+n+1,cmp);
	for(i=1;i<=n;i++)
		fprintf(g,"%.6lf %.6lf\n",v[i].x,v[i].y);
	
	return 0;
}