Cod sursa(job #2535632)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 1 februarie 2020 09:58:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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

struct vec2{
	double x, y;
	bool bye = false;
};

int n;
double det(vec2 a, vec2 b, vec2 c){
	return (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y);
}

bool cmp(const vec2 &lhs, const vec2 &rhs){
	return lhs.x < rhs.x;
}

vector<vec2> wa;
vector<int> ans;
bool chec(int a){
	int s = ans.size();
	if(s <= 1){
		return true;
	}else{
		return det(wa[ans[s-2]], wa[ans[s-1]], wa[a]) >= 0;
	}
}

void yeet(){
	for(int i = 0; i < n; ++i){
		while(!chec(i)){
			wa[ans.back()].bye = false;
			ans.pop_back();
		}
		wa[i].bye = true;
		ans.push_back(i);
	}
	for(int i = n-1; i >= 0; --i){
		if(!wa[i].bye){
			while(!chec(i)){
				wa[ans.back()].bye = false;
				ans.pop_back();
			}
			wa[i].bye = true;
			ans.push_back(i);
		}
	}
}

int main(){
	fin >> n;
	for(int i = 0; i < n; ++i){
		vec2 a;
		fin >> a.x >> a.y;
		wa.push_back(a);
	}
	sort(wa.begin(), wa.end(), cmp);
	yeet();
	
	fout << fixed << setprecision(6);
	fout << ans.size() << "\n";
	for(auto a : ans){
		vec2 b = wa[a];
		fout << b.x << " " << b.y << "\n";
	}
	return 0;
}