Cod sursa(job #1395365)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 21 martie 2015 11:20:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;

#define NMAX 120001
#define INF (1<<30)
#define eps 0.0000000001

struct punct {
	double x,y;
	punct() {
		x=0;
		y=0;
	}
	punct(double _x, double _y) {
		x=_x;
		y=_y;
	}
};

inline double cross_product(punct a, punct b, punct c) 
{
	return (double)(b.x-a.x)*(c.y-a.y)-(double)(c.x-a.x)*(b.y-a.y);
}

struct cmp {
	bool operator () (const punct &a, const punct &b) const {
		if(fabs(a.x-b.x)<=eps)
			return true;
		else return a.x<b.x;
	}
};

punct v[NMAX],sus[NMAX],jos[NMAX];

int main ()
{
	int i,n,n1,n2,k;
	double s,j,maxy,miny;
	punct a,b,c,q;
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f>>n;
	for(i=1;i<=n;i++) 
		f>>v[i].x>>v[i].y;
	f.close();
	sort(v+1,v+n+1,cmp());
	n1=n2=0;
	k=0;
	s=0;
	while(k+1<=n) {
		k++;
		j=v[k].x;
		maxy=v[k].y;
		miny=v[k].y;
		while(fabs(v[k+1].x-j)<=eps && k+1<=n) {
			k++;
			maxy=max(maxy,v[k].y);
			miny=min(miny,v[k].y);
		}
		while(n1>=2 && cross_product(sus[n1-1],sus[n1],punct(j,maxy))>0) {
			s=s+(double)fabs(cross_product(sus[n1-1],sus[n1],punct(j,maxy)))/2.0;
			n1--;
		}
		while(n2>=2 && cross_product(jos[n2-1],jos[n2],punct(j,miny))<0) {
			s=s+(double)fabs(cross_product(jos[n2-1],jos[n2],punct(j,miny)))/2.0;
			n2--;
		}
		sus[++n1]=punct(j,maxy);
		jos[++n2]=punct(j,miny);
	}
	k=1;
	if(fabs(sus[1].x-jos[1].x)<=eps && fabs(sus[1].y-jos[1].y)<=eps)
		k=2;
	if(fabs(sus[n1].x-jos[n2].x)<=eps && fabs(sus[n1].y-jos[n2].y)<=eps)
		n1--;
	g<<n1+n2-k+1<<'\n';
	for(i=1;i<=n2;i++) {
		g<<fixed;
		g<<setprecision(6)<<jos[i].x<<" "<<jos[i].y<<'\n';
	}
	for(i=n1;i>=k;i--) {
		g<<fixed;
		g<<setprecision(6)<<sus[i].x<<" "<<sus[i].y<<'\n';
	}
	g.close();
	return 0;
}