Cod sursa(job #1898527)

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

using namespace std;

ifstream fin("infasuratoarea.in");
ofstream fout("infasuratoarea.out");
struct point{
	double x,y;
	
}A[125000],sr;
int N,mpoz;
stack <point> s;
long long dist(point a,point b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); 
	
}

int direct(point p,point q,point r){
	int val=(q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);
	if (val==0) return 0;//colinear
	else {
		if (val>0) return 1;//clockwise
		else return 2;//conterlock wise
		
	}
	
}
bool comp(point a,point b){
	int v=direct(sr,a,b);
	if (v==0){
		if (dist(sr,b)>=dist(sr,a)) return 0;
		else return 1;
	}
	else {
		if (v==2) return 0;
		else return 1;
	}

}

point nexttotop(){
		point p=s.top();
		s.pop();
		point res=s.top();
		s.push(p);
		return res;
}

int main(){
	
	fin >>N;
	sr.x=sr.y=1e10;
	
	for (int i=1;i<=N;i++){
		fin >>A[i].x>>A[i].y;
			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);
	//for (int i=1;i<=N;i++) cout <<A[i].x<<" "<<A[i].y<<endl;
	
	s.push(A[1]);
	s.push(A[2]);
	s.push(A[3]);
	//for (int i=3;i<=N;i++) cout <<direct(A[i-2],A[i-1],A[i])<<" ";
	
	for (int i=4;i<=N;i++){
		//cout <<s.size()<<" ";
		while (direct(nexttotop(),s.top(),A[i])==2 && s.size()>3){
			s.pop();
		}
		s.push(A[i]);
	}
	
	fout <<s.size()<<endl;
	
	while (!s.empty()) {
		point x=s.top();;
		fout <<fixed <<setprecision(6)<<x.x<<" "<<x.y<<"\n";
		s.pop();
	}
	
	return  0;
	
}