Cod sursa(job #3195728)

Utilizator RusuRRusu Rares RusuR Data 21 ianuarie 2024 16:03:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

std::ifstream f("infasuratoare.in");
std::ofstream g("infasuratoare.out");

struct coord{
	double y, x;
};
int n;
std::vector<coord> v,s;
double orientation(const coord& a, const coord& b, const coord& c){
	return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool trigComp(const coord& a, const coord& b){
	return orientation(v[0],a,b)<0;
}

int main(){
	f>>n;
	double mx=DBL_MAX;
	int mi=0;
	for(int i=0;i<n;i++){
		double a, b;
		f>>a>>b;
		if(a<mx){
			mx=a;
			mi=i;
		}
		v.push_back({a,b});
	}
	std::swap(v[0],v[mi]);
	std::sort(v.begin()+1,v.end(),trigComp);
	s.push_back(v[0]);
	s.push_back(v[1]);
	for(int i=2;i<n;i++){
		int h=s.size()-1;
		while(h>=1 && orientation(s[h-1],s[h],v[i])>0){
			h--;
			s.pop_back();
		}
		s.push_back(v[i]);
	}
	g<<s.size()<<'\n';
	g<<std::setprecision(12)<<std::fixed;
	while(!s.empty()){
		g<<s.back().y<<' '<<s.back().x<<'\n';
		s.pop_back();
	}
	return 0;
}