Cod sursa(job #1721674)

Utilizator valentin50517Vozian Valentin valentin50517 Data 26 iunie 2016 12:46:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<double,double> pdd;
pdd V[120100],St[120100];
inline double cww(const pdd &a,const pdd &b,const pdd &c){return (b.x -a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);}
bool cmp(const pdd &a,const pdd &b){ return cww(V[1],a,b) < 0;}
int st,N,poz=1;
int main(){
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	cin >> N;
	for(int i = 1;i<=N;i++){
		cin >> V[i].x >> V[i].y;
		if(V[i] < V[poz]) poz = i;
	}
	swap(V[1],V[poz]);
	sort(V+2,V+N+1,cmp);
	St[1] = V[1];
	St[2] = V[2];
	st = 2;
	for(int i = 3;i<=N;++i){
		while(st >= 2 && cww(St[st-1],St[st],V[i]) > 0) --st;
		St[++st] = V[i];
	}
	cout <<  st << fixed << setprecision(9) << '\n';
	while(st>0) {cout << St[st].x << ' ' << St[st].y << '\n';--st;}
	
	
	return 0;
}