Cod sursa(job #682023)

Utilizator johnny2008Diaconu Ion johnny2008 Data 18 februarie 2012 14:37:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define pb push_back

int n;
stack<int> x;
stack<int> y;
vector<int> sol[120001];
struct punct{
	double x;
	double y;
};
punct pun[120001];
bool cmp(punct a,punct b){
	if(a.y<b.y)
		return true;
	if(a.y==b.y && a.x<b.x)
		return true;
	return false;
}
void dr( int ul, int pen, double &a, double &b, double &c) {
	a=pun[ul].y-pun[pen].y;
	b=pun[pen].x-pun[ul].x;
	c=pun[ul].x*pun[pen].y-pun[pen].x*pun[ul].y;
	
}
int main(){
	int i,j;
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f>>n;
	g.precision(20);
	for(i=1;i<=n;i++){
		f>>pun[i].x>>pun[i].y;
		
	}
	sort(pun+1,pun+n+1,cmp);
	/*for(i=1;i<=n;i++){
		cout<<pun[i].x<<" "<<pun[i].y<<"\n";
		
	}
	
	cout<<"\n";
	*/
	x.push(1);
	x.push(2);
	int ul=2,pen=1;
	for(i=3;i<=n;i++){
		double a,b,c;
		dr( ul, pen, a, b, c);
		//cout<<ul<<" "<<pen<<"\n";
		while(a*pun[i].x+b*pun[i].y+c>0 && x.size()>2){
			ul=pen;
			
			x.pop();
			x.pop();
			pen=x.top();
			x.push(ul);
			dr( ul, pen, a, b, c);
			
		}

		if(a*pun[i].x+b*pun[i].y+c>0){
			x.pop();
			pen=x.top();
			ul=i;
			x.push(i);
		}
		else{
			x.push(i);
			pen=ul;
			ul=i;
		}
		
	}
	
	
	y.push(1);
	y.push(2);
	ul=2,pen=1;
	for(i=3;i<=n;i++){
		double a,b,c;
		dr( ul, pen, a, b, c);
		//cout<<ul<<" "<<pen<<"\n";
		
		while(a*pun[i].x+b*pun[i].y+c<0 && y.size()>2){
			ul=pen;
			
			y.pop();
			y.pop();
			pen=y.top();
			y.push(ul);
			dr( ul, pen, a, b, c);
			
		}
		//cout<<"\n";
		if(a*pun[i].x+b*pun[i].y+c<0){
			//cout<<a<<" "<<b<<" "<<c<<"\n";
			y.pop();
			pen=y.top();
			ul=i;
			y.push(i);
		}
		else{
			y.push(i);
			pen=ul;
			ul=i;
		}
		
	}
	int sol[100000],ct=0,lol[100000];
	while(x.size()){
		ct++;
		lol[ct]=x.top();
		x.pop();
	}
	for(i=ct;i>0;i--){
		sol[ct-i+1]=lol[i];
	
	}
	y.pop();
	while(y.size()>1){
		ct++;
		sol[ct]=y.top();
		y.pop();
	}
	g<<ct<<"\n";
	for(i=1;i<=ct;i++){
		g<<pun[sol[i]].x<<" "<<pun[sol[i]].y<<"\n";
	}
	return 0;
}