Cod sursa(job #2659567)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 17 octombrie 2020 09:47:40
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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

struct vec2{
	double x, y;
};

double det(vec2 v1, vec2 v2, vec2 v3){
	return (v2.x-v1.x)*(v3.y-v1.y)
	      -(v3.x-v1.x)*(v2.y-v1.y);
}

int n;
vec2 vex[120041];
bool vi[120041];

bool cmp(const vec2 &v1, const vec2 &v2){
	if(v1.x != v2.x) return v1.x < v2.x;
	else             return v1.y < v2.y;
}

void read(){
	fin >> n;
	for(int i = 0; i < n; ++i){
		vec2 &v = vex[i];
		fin >> v.x >> v.y;
	}
}

struct yip{
	vec2 v;
	int p;
};

yip makeyip(int i){
	return {vex[i],i};
}

vector<yip> hulio;
bool isgood(vec2 v){
	int s = hulio.size();
	return det(hulio[s-2].v, hulio[s-1].v, v)>0;
}

void solve(){
	sort(vex, vex+n, cmp);
	hulio.push_back(makeyip(0));
	vi[0] = true;
	hulio.push_back(makeyip(1));
	vi[1] = true;
	for(int i = 2; i < n; ++i){
		while(hulio.size() >= 2 && !isgood(vex[i])){
			vi[hulio.back().p] = false;
			hulio.pop_back();
		}
		hulio.push_back(makeyip(i));
		vi[i] = true;
	}
	
	for(int i = n-1; i >= 0; --i){
		if(vi[i])continue;
		while(hulio.size() >= 2 && !isgood(vex[i])){
			vi[hulio.back().p] = false;
			hulio.pop_back();
		}
		hulio.push_back(makeyip(i));
		vi[i] = true;
	}
}

void write(){
	fout << hulio.size() << "\n";
	fout << fixed << setprecision(6);
	for(auto &yi : hulio){
		fout << yi.v.x << " " << yi.v.y << "\n";
	}
}

int main(){
	// ios_base::sync_with_stdio(false);
	read();
	solve();
	write();
	return 0;
}