Cod sursa(job #967891)

Utilizator dropsdrop source drops Data 28 iunie 2013 18:07:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("infasuratoare.in");
ofstream gg("infasuratoare.out");

#define max 120001
#define eps 1e-12

struct pct{ double x,y; pct(double x0=0,double y0=0){x=x0;y=y0;} 
	void af(){ cout << "(" << x << "," << y << ") "; }} ss[max], su[max], sd[max];
int n, n1, n2;

bool cmp(pct a, pct b){ return a.x<b.x; }

double dlt(pct a, pct b, pct c){
	return a.x*b.y+b.x*c.y+c.x*a.y-b.x*a.y-c.x*b.y-a.x*c.y;
}

void sub(){
	su[n1++]=sd[n2++]=ss[0];
	for(int i=1;i<n-1;i++)
	if(dlt(ss[0],ss[n-1],ss[i]) > 0) su[n1++]=ss[i]; else
	if(dlt(ss[0],ss[n-1],ss[i]) < 0) sd[n2++]=ss[i];
	su[n1++]=sd[n2++]=ss[n-1];
}

void sup(){
	int n=2;
	for(int i=2;i<n1;i++){
		while(n>=2 && dlt(su[n-2],su[i],su[n-1]) < eps)n--; // dlt<=0 (0==eps)
		su[n++]=su[i];
	}
	n1=n;
}

void sdo(){
	int n=2;
	for(int i=2;i<n2;i++){
		while(n>=2 && dlt(sd[n-2],sd[i],sd[n-1]) > -eps)n--; // dlt>=0 (0==-eps)
		sd[n++]=sd[i];
	}
	n2=n;
}

int main(){
	ff >> n;
	for(int i=0;i<n;i++) ff >> ss[i].x >> ss[i].y;
	sort(ss, ss+n, cmp);
	sub();
	sup();
	sdo();
	gg << n1+n2-2 << "\n";
	gg << setprecision(6) << fixed;
	for(int i=n1-1;i>=0;i--) gg << su[i].x << " " << su[i].y << "\n";
	for(int i=1;i<n2-1;i++) gg << sd[i].x << " " << sd[i].y << "\n";
	return 0;
}