Cod sursa(job #2183430)

Utilizator DimaTCDima Trubca DimaTC Data 23 martie 2018 10:09:37
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<bits/stdc++.h>
#define x first
#define y second
#define NMAX 120100

using namespace std;

typedef pair<double,double> pii;
pii a[NMAX];
int s[NMAX];
int mn,n;

double crossProduct(pii O, pii L, pii R) {
	return (L.x-O.x)*(R.y-O.y)-(L.y-O.y)*(R.x-O.x);
}

bool cmp(pii l, pii r) {
	return crossProduct(a[1],l,r)>0;
}

int main() {
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	cin>>n;
	a[0].x=a[0].y=1e9;
	for (int i=1; i<=n; i++) {
		cin>>a[i].x>>a[i].y;
		if (a[i].x<a[mn].x || a[i].x==a[mn].x && a[i].y<a[mn].y) mn=i;
	}
	swap(a[mn],a[1]);
	sort(a+2,a+1+n,cmp);
	
	s[1]=1; s[2]=2; int i=3; int p=3; int last=2;
	for (int i=3; i<=n; i++) {
		while (last>=3 && crossProduct(a[s[last]],a[i],a[s[last-1]])<0) last--;
		s[++last]=i;
	}
	
	cout<<last<<'\n';
	for (int i=1; i<=last; i++) {
		cout<<fixed<<setprecision(10)<<a[s[i]].x<<" "<<a[s[i]].y<<'\n';
	}
	
	
	return 0;
}