Cod sursa(job #2641685)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 12 august 2020 13:14:23
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define det(a,b,c,d,e,f) a*d+b*e+c*f-e*d-a*f-c*b                                                                                                            

using namespace std;

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

int n;
pair<long double, long double> a[120010];
stack<int> St;

long double dist(long double a0,long double a1,long double b0,long double b1){
	return sqrt((b0-a0)*(b0-a0)+(b1-a1)*(b1-a1));
}

pair<long double,long double> caos(pair<long double, long double> A){
		return {(a[1].second-A.second)/dist(A.first,A.second,a[1].first,a[1].second),dist(A.first,A.second,a[1].first,a[1].second)};
}

bool comp(pair<long double, long double> A,pair<long double, long double> B){
	return (caos(A)>caos(B));
}

bool ok(int poz){
	int B=St.top();St.pop();
	int A=St.top();St.push(B);
	return (det(a[A].first,a[A].second,a[B].first,a[B].second,a[poz].first,a[poz].second)<=0);
}

int main(){
	f>>n;
	for(int i=1;i<=n;i++){
		f>>a[i].first>>a[i].second;
	}
	sort(a+1,a+n+1);
	sort(a+2,a+n+1,comp);
	St.push(1);
	St.push(2);
	for(int i=3;i<=n;i++){
		while(St.size()>=2&&ok(i))
			St.pop();
		St.push(i);
	}
	vector<int> v;
	while(St.size()){
		v.push_back(St.top());
		St.pop();
	}
	reverse(v.begin(),v.end());
	g<<v.size()<<'\n';
	for(auto it:v)
		g<<fixed<<setprecision(6)<<a[it].first<<' '<<a[it].second<<'\n';
}