Cod sursa(job #2185601)

Utilizator alex.info99polimernic alex.info99 Data 24 martie 2018 18:03:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define p pair<double,double>
using namespace std;
const int N=200020;
p v[N], h[N];
int j;
bool s(p a, p b, p c){
	return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)<0;
}
int main(){
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	int n;
	f>>n;
	for(int i=0;i<n;i++)f>>v[i].x>>v[i].y;
	sort(v, v+n);
	reverse_copy(v,v+n-1,v+n);
	int i, m=2*n-1;
	for(i=0;i<m;h[j++]=v[i++]) while(j>1 && s(h[j-2], h[j-1],v[i]))--j;
	g<<--j<<endl;
	g<<setprecision(6)<<fixed;
	for(int i=0;i<j;i++)g<<h[i].x<<' '<<h[i].y<<endl;
	return 0;
}