Cod sursa(job #967814)

Utilizator dropsdrop source drops Data 28 iunie 2013 15:58:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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 <algorithm>
using namespace std;
ifstream ff("test.in");
//ofstream gg("test.out");
#define gg cout
#define max 120001
#define eps 1e-8

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])>eps) su[n1++]=ss[i]; else
	if(dlt(ss[0],ss[n-1],ss[i])<eps) 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--; 
		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--;
		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();
	cout << n1+n2-2 << "\n";
	for(int i=n1-1;i>=0;i--) cout << su[i].x << " " << su[i].y << "\n";
	for(int i=1;i<n2-1;i++) cout << sd[i].x << " " << sd[i].y << "\n";
	return 0;
}