Cod sursa(job #2480036)

Utilizator TRIST0248SASASASA TRIST0248 Data 24 octombrie 2019 19:49:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
#define INF 1e9+7
#define LINf 1e18+7
#define fr first 
#define sc second
#define ll long long
#define pb push_back
#define pii pair<int,int>

using namespace std;
vector< pair<double,double> > pn;
pair<double,double> up[200005],dw[200005];
int pu , pd;
int n;
int tr(pair<double,double> a , pair<double,double> b , pair<double,double> c){
	if(a.fr*b.sc + b.fr*c.sc + c.fr*a.sc - a.fr*c.sc - b.fr*a.sc - c.fr*b.sc < 0)return -1;
	return 1;	
}
void psu(pair<double,double> nx){
	if(pu < 2){
		pu++;
		up[pu] = nx;
	}else{
		if(tr(up[pu-1],up[pu],nx) == -1){
			pu--;
			psu(nx);
		}else{
			pu++;
			up[pu] = nx;
		}
	}
}
void psd(pair<double,double> nx){
	if(pd < 2){
		pd++;
		dw[pd] = nx;
	}else{
		if(tr(dw[pd-1],dw[pd],nx) == 1){
			pd--;
			psd(nx);
		}else{
			pd++;
			dw[pd] = nx;
		}
	}
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	fin >> n;
	double x, y;
	for(int i = 1; i <= n ; i++){
		fin >> x >> y;
		pn.pb({x,y});
	}
	sort(pn.begin(),pn.end());
	pu = 1, pd = 1;
	up[pu] = pn[0];
	dw[pd] = pn[0];
	for(int i = 1 ; i < n - 1 ; i++){
		if(tr(pn[0],pn[i],pn[n-1])==1){
			psu(pn[i]);
		}else{
			psd(pn[i]);
		}
	}
	psu(pn[n-1]);
	psd(pn[n-1]);
	fout << setprecision(12);
	fout << pu + pd - 2 << '\n';
	for(int i = 2 ; i <= pu ; i++){
		fout << up[i].fr << " " << up[i].sc << '\n';
	}
	for(int i = pd - 1; i > 1 ; i--){
		fout << dw[i].fr << " " << dw[i].sc << '\n';
	}
}