Cod sursa(job #982707)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 9 august 2013 19:00:13
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 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.0000001

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(nr>=2 && cross_product(a[nr-1],a[nr],v[i])<0)
			nr--;
		a[++nr]=v[i];
	}
	a[++nr]=a[1];
	return nr;
}

long double modul(long double x)
{
	if(x<=0)
		return -x;
	return x;
}

long double dist(double A, double B, double C, punct x)
{
	return (long double)(modul(0LL+1LL*A*x.x+1LL*B*x.y+C))/sqrtl(0LL+1LL*A*A+1LL*B*B);
}

double dist2(punct x, punct y)
{
	return (double)sqrtl(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++) {
		v[i]=a[i];
		cout<<a[i].x<<" "<<a[i].y<<endl;
	}
	n=nr;
	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)>d2)
					d2=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>d3)
					d3=min(a[i].y,a[i+1].y)-v[j].y;
			}
			if((double)1LL*(0LL+d2+d3+fabs(a[i].y-a[i+1].y))*d1<sol)
				sol=(double)1LL*(0LL+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);
			if(egal(A,0))
				AA=INF;
			else {
				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(AA!=INF) {
					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]);
				}
				else {
					if(egal(modul(a[i].x-v[j].x)+modul(a[i+1].x-v[j].x),dist2(a[i],a[i+1])))
						continue;
					if(modul(a[i].x-v[j].x)<modul(a[i+1].x-v[j].x)) {
						if(modul(a[i].x-v[j].x)>d2)
							d2=modul(a[i].x-v[j].x);
					}
					else if(modul(a[i+1].x-v[j].x)>d3)
						d3=modul(a[i+1].x-v[j].x);
				}
			}
			if((double)(0LL+d2+d3+1LL*dist2(a[i],a[i+1]))*d1<sol)
				sol=(double)(0LL+d2+d3+1LL*dist2(a[i],a[i+1]))*d1;
		}
	}
	g<<fixed;
	g<<setprecision(2)<<sol;
	return 0;
}