Cod sursa(job #2116643)

Utilizator DimaTCDima Trubca DimaTC Data 27 ianuarie 2018 20:11:03
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<bits/stdc++.h>
#define NMAX 120015
#define x first 
#define y second
using namespace std;

typedef pair<double, double>point;
int n,m;
point a[NMAX];
point s[NMAX];

double crossProduct(point A, point B, point C) {
	return (A.x-C.x)*(B.y-C.y)-(B.x-C.x)*(A.y-C.y);
}

bool cmp(point A, point B) {
	return crossProduct(A,B,a[1])<0;
}
 
void sortAngle() {
	int pos=1;
	for (int i=2; i<=n; i++) {
		if (a[i].x<a[pos].x || a[i].x==a[pos].x && a[i].y<a[pos].y) pos=i;
	}
	swap(a[1],a[pos]);
	
	sort(a+2, a+1+n, cmp);
}

int main() {
	ifstream cin("infasuratoare.out");
	ofstream cout("infasuratoare.out");
	
	cin>>n;
	
	for (int i=1; i<=n; i++) {
		cin>>a[i].x>>a[i].y;
	}
	sortAngle();
	
	s[1]=a[1]; s[2]=a[2]; int last=2;
	for (int i=3; i<=n; i++) {
		while (crossProduct(s[last-1],s[last],a[i])>0) {
			last--;
		}	
		s[++last]=a[i];
	}
	cout<<last<<'\n';
	for (int i=last; i>=1; i--) {
		cout<<fixed<<setprecision(13)<<s[i].x<<" "<<s[i].y<<"\n";
	}
	
	
	return 0;
}