Cod sursa(job #1898598)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 2 martie 2017 09:49:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point{
	double  x,y;
	
}stk[121000],A[121000],sr;
int N,mpoz,hd;

void read(){
	fin >>N;
	for (int i=1;i<=N;i++) fin >>A[i].x>>A[i].y;
}

double cross(point a,point b,point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool comp(point a,point b){
	return (cross(A[1],a,b))<0;
}

void arrange(){
	sr=A[1];
	mpoz=1;
		for (int i=2;i<=N;i++){
			if (A[i].x<sr.x || (A[i].x==sr.x && A[i].y<sr.y)){
				sr=A[i];
				mpoz=i;
			}
		}
	swap(A[1],A[mpoz]);
	sort(A+2,A+N+1,comp);
}

void solve(){
	arrange();
	stk[1]=A[1];
	stk[2]=A[2];
	hd=2;
	for (int i=3;i<=N;i++){
		while (hd>=2 && cross(stk[hd-1],stk[hd],A[i])>0) --hd;
		stk[++hd]=A[i];
	}
	
}

void afis(){
	fout <<hd<<endl;
	for (int i=hd;i>=1;i--) fout <<fixed<<setprecision(9)<<stk[i].x<<" "<<stk[i].y<<"\n";
	
}

int main(){
	read();
	solve();
	afis();
	
	return 0;
	
}