Cod sursa(job #2984715)

Utilizator ViAlexVisan Alexandru ViAlex Data 24 februarie 2023 18:36:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include<iostream>
#include<deque>
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;

struct point{
	double x,y;
};

bool compare1(const point&a, const point&b){
	return a.x<b.x || (a.x==b.x && a.y<b.y);
}

bool compare2(const point&a, const point&b){
	return a.x>b.x || (a.x==b.x && a.y>b.y);
}

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int n;
vector<point> points;

void read(){
	in>>n;
	points.resize(n);
	for(int i=0;i<n;i++){
		in>>points[i].x>>points[i].y;
	}
}

/*  1   1    1
 * a.x b.x  c.x
 * a.y b.y  c.y
 */

double determinant(point a, point b, point c){
	return (b.x*c.y) + (a.x*b.y) + (a.y*c.x) - (b.x*a.y) - (c.x*b.y) - (c.y*a.x);
}

vector<point> get_hull(){
	vector<point> hull; 
	hull.push_back(points[0]);
	hull.push_back(points[1]);

	for(int i=2;i<n;i++){
		while(hull.size()>=2 && determinant(hull[hull.size()-2],hull[hull.size()-1],points[i])<=0 ){
			hull.pop_back();		
		}

		hull.push_back(points[i]);
	}
	return hull;
}



void solve(){
	sort(points.begin(),points.end(),compare1);
	vector<point> lower = get_hull();
	sort(points.begin(),points.end(),compare2);
	vector<point> upper = get_hull();

	lower.pop_back();
	upper.pop_back();

	out<<lower.size()+upper.size()<<'\n';

	for(point a:lower){
		out<<fixed<<setprecision(10)<<a.x<<" "<<a.y<<'\n';
	}

	for(point a:upper){
		out<<fixed<<setprecision(10)<<a.x<<" "<<a.y<<'\n';
	}
}


int main(){
	read();
	solve();

	return 0;
}