Cod sursa(job #2233055)

Utilizator b10nd3Oana Mancu b10nd3 Data 22 august 2018 00:58:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<iostream>
#include<fstream>
#include<iomanip>
#include<algorithm>

//convexHull
using namespace std;

#define x first
#define y second

typedef pair<double,double> Point;
int n;
Point start;

double crossProduct(Point a, Point b, Point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(Point x, Point y){
	return crossProduct(start,x,y)<0;
}

int main(){
    ifstream in("infasuratoare.in");
	ofstream out("infasuratoare.out"); 	
	
	int i,poz,last;
	
	in>>n;
	Point p[n+1], stack[n+1];
	for( i=1;i<=n;i++) in>>p[i].x>>p[i].y;
	
	//cel mai din stanga jos: p[1]=start
	poz=1;
	for(i=2;i<=n;i++)
	   if(p[poz]>p[i]) poz=i;
	swap(p[1],p[poz]);
	start=p[1];
	
	//sortare dupa unghiul polar cu start
	sort(p+2,p+n+1,cmp);  
	//for(i=1;i<=n;i++) cout<<p[i].x<<" "<<p[i].y<<endl; //checked
	
	//cat timp pct curent <(unghi theta) penultimul: sterge din stiva; adauga pct curent 
	stack[1]=p[1]; stack[2]=p[2]; last=2;
	for(i=3;i<=n;i++){
		while(last>=2 && crossProduct(stack[last-1],stack[last],p[i])>0)
		    last--;
		stack[++last]=p[i];    
	} 
	
	out<<fixed<<last<<'\n';
	for(i=last;i>0;i--) 
	    out<<setprecision(12)<<stack[i].x<<" "<<stack[i].y<<'\n';
	
	in.close(); out.close();
	return 0;
}