Cod sursa(job #982686)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 9 august 2013 18:35:32
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<math.h>
using namespace std;

#define NMAX 100001
#define INF (1LL<<60)
#define eps 0.0001

struct punct {
	int x,y;
};

punct v[NMAX],a[NMAX];

long long cross_product(punct a, punct b, punct c)
{
	return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);
}

struct cmp {
	bool operator () (const punct &a, const punct &b) {
		return cross_product(v[1],a,b)>0;
	}
};

int graham_scan(int n)
{
	int nr,i;
	for(i=2;i<=n;i++)
		if(v[i].y<v[1].y || (v[i].y==v[1].y && v[i].x<v[1].x)) 
			swap(v[1],v[i]);
	sort(v+2,v+n+1,cmp());
	a[1]=v[1];
	a[2]=v[2];
	nr=2;
	for(i=3;i<=n;i++) {
		while(cross_product(a[nr-1],a[nr],v[i])<0)
			nr--;
		a[++nr]=v[i];
	}
	a[++nr]=a[1];
	return nr;
}

double dist(double A, double B, double C, punct x)
{
	return (double)(fabs(A*x.x+B*x.y+C))/sqrt(A*A+B*B);
}

double minim(double x, double y)
{
	if(x<=y)
		return x;
	return y;
}

double maxim(double x, double y)
{
	if(x>=y)
		return x;
	return y;
}

double dist2(punct x, punct y)
{
	return (double)sqrt(1LL*(x.x-y.x)*(x.x-y.x)+1LL*(x.y-y.y)*(x.y-y.y));
}

int egal(double x, double y)
{
	if(fabs(x-y)<=eps)
		return 1;
	return 0;
}

int main ()
{
	int n,i,nr,j;
	double d1,d2,d3,sol,A,B,C,AA,C1,C2;
	ifstream f("rubarba.in");
	ofstream g("rubarba.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i].x>>v[i].y;
	f.close();
	nr=graham_scan(n);
	sol=INF;
	for(i=1;i<=nr;i++) {
		d1=0;
		d2=0;
		d3=0;
		if(a[i].x==a[i+1].x) {
			for(j=1;j<=n;j++) {
				if(fabs(v[j].x-a[i].x)>d1)
					d1=fabs(v[j].x-a[i].x);
				if(v[j].y>max(a[i].y,a[i+1].y) && v[j].y-max(a[i].y,a[i+1].y)>d1)
					d1=v[j].y-max(a[i].y,a[i+1].y);
				if(v[j].y<min(a[i].y,a[i+1].y) && min(a[i].y,a[i+1].y)-v[j].y>d2)
					d2=min(a[i].y,a[i+1].y)-v[j].y;
			}
			if((double)(d2+d3+fabs(a[i].y-a[i+1].y))*d1<sol)
				sol=(double)(d2+d3+fabs(a[i].y-a[i+1].y))*d1;
		}
		else {
			A=(double)(a[i+1].y-a[i].y)/(a[i+1].x-a[i].x);
			B=-1;
			C=(double)(a[i].y-A*a[i].x);
			AA=(double)(-1)/A;
			C1=(double)(a[i].y-AA*a[i].x);
			C2=(double)(a[i+1].y-AA*a[i+1].x);
			for(j=1;j<=n;j++) {
				if(dist(A,B,C,v[j])>d1)
					d1=dist(A,B,C,v[j]);
				if(egal(dist(AA,-1,C1,v[j])+dist(AA,-1,C2,v[j]),dist2(a[i],a[i+1])))
					continue;
				if(dist(AA,-1,C1,v[j])<dist(AA,-1,C2,v[j])) {
					if(dist(AA,-1,C1,v[j])>d2)
						d2=dist(AA,-1,C1,v[j]);
				}
				else if(dist(AA,-1,C2,v[j])>d3)
					d3=dist(AA,-1,C2,v[j]);
			}
			if((double)(d2+d3+dist2(a[i],a[i+1]))*d1<sol)
				sol=(double)(d2+d3+dist2(a[i],a[i+1]))*d1;
		}
	}
	g<<fixed;
	g<<setprecision(2)<<sol;
	return 0;
}