Cod sursa(job #2404262)

Utilizator MaarcellKurt Godel Maarcell Data 12 aprilie 2019 14:19:36
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
#include <complex>
#include <cassert>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define deb(a) cerr<< #a << "= " << (a)<<"\n";

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef complex<double> base;
typedef vector<int> vi;
typedef pair<int,int> pii;

template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
ll inv(ll a, ll b){ return a<2 ? a : ((a-inv(b%a,a))*b+1)/a%b; }
int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}


struct point{
	ld x,y;
};



int N,K; point a[130000],st[130000];

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

ld sdist(point A, point B){
	return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

bool cmp(point A, point B){
	ld s = area(a[1],A,B);
	if (s==0) return sdist(a[1],A)<sdist(a[1],B);
	else return s>0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	
	cin >> N;
	
	int i,ind=1;
	for (i=1; i<=N; i++){
		cin >> a[i].x >> a[i].y;
		
		if (a[i].x<a[ind].x)
			ind = i;
	}
	
	swap(a[ind],a[1]);
	sort(a+2,a+N+1,cmp);
	
	st[++K]=a[1];
	st[++K]=a[2];
	
	for (i=3; i<=N; i++){
		while (K>1 && area(st[K-1],st[K],a[i])<0)
			K--;
			
		st[++K]=a[i];
	}
	
	cout << fixed << setprecision(10);
	cout << K << "\n";
	for (i=1; i<=K; i++)
		cout << st[i].x << " " << st[i].y << "\n";
	
}