Cod sursa(job #377668)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 25 decembrie 2009 19:35:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <algorithm>
#define MAX 120010
#define cx first
#define cy second
using namespace std;
pair<double,double> v[MAX];
int puncte[MAX];
int N,pstart,xref,yref;
int st[MAX];


inline bool cmp(int p1,int p2){
	return ((long double)(v[p1].cy-yref)*(v[p2].cx-xref)<(long double)(v[p1].cx-xref)*(v[p2].cy-yref));
}

inline bool good_turn(int p1,int p2,int p3){
	long double produs=(long double)(v[p1].cx)*(v[p2].cy)+(long double)(v[p2].cx)*(v[p3].cy)+(long double)(v[p3].cx)*(v[p1].cy)
		-(long double)(v[p1].cx)*(v[p3].cy)-(long double)(v[p3].cx)*(v[p2].cy)-(long double)(v[p2].cx)*(v[p1].cy);
	if (produs>0) return true; else return false;
}

int main(){
	pstart=xref=yref=0;
	
	ifstream fi("infasuratoare.in");
	fi>>N;
	for (int i=1;i<=N;++i){
		fi>>v[i].cx>>v[i].cy;
		if (pstart==0 || (v[i].cx<xref) || (v[i].cx==xref && v[i].cy<yref)) { pstart=i; xref=v[i].cx; yref=v[i].cy; }
	}
	fi.close();
	--xref;

	int NP=0;
	for (int i=1;i<=N;++i) if (i!=pstart) puncte[++NP]=i;
	sort(puncte+1,puncte+NP+1,cmp);

	int vf=1;
	st[1]=pstart;
	for (int i=1;i<=NP;++i){
		while (vf>=2 && good_turn(st[vf-1],st[vf],puncte[i])==false) --vf;
		st[++vf]=puncte[i];
	}
	
	ofstream fo("infasuratoare.out");
	fo<<vf<<"\n";
	fo.precision(22);
	for (int i=1;i<=vf;++i) fo<<v[st[i]].cx<<" "<<v[st[i]].cy<<"\n";
	fo.close();
	return 0;
}