Cod sursa(job #1921482)

Utilizator wilson182Alexandrina Panfil wilson182 Data 10 martie 2017 12:53:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<double,double> pt;
const int N=240020;
int n, j;
pt a[N], h[N];
int crossproduct(pt a, pt b, pt c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)<0;
}
bool cmp(int a1, int b){
	return(a[a1].x< a[b].x);
}
int main(){
	int cx, cmx;
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f>>n;
	for(int i=0;i<n;i++)f>>a[i].x>>a[i].y;
	sort(a, a+n);
	reverse_copy(a, a+n-1, a+n);
	int i;
	for( i=0;i<2*n-1;h[j++]=a[i++])
	while(j>1 && crossproduct(h[j-2], h[j-1], a[i])) --j;
	g<<--j<<endl;
	g<<setprecision(6)<<fixed;
	for(i=0;i<j;i++)g<<h[i].x<<' '<<h[i].y<<endl;
	return 0;
}