Cod sursa(job #658358)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 8 ianuarie 2012 17:55:18
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const double inf=1000000000000.0;

int n;
struct str{double x, y;} a[100010],hull[100010];

inline bool cmp(const str &P,const str &Q){return atan2(P.y-a[1].y,P.x-a[1].x)<atan2(Q.y-a[1].y,Q.x-a[1].x);}
inline double det(const str &a,const str &b,const str &c) {return 1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y-1LL*a.x*c.y-1LL*b.x*a.y-1LL*c.x*b.y;}
inline double dist(str a, str b){double ans = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);return sqrt(ans);}
inline int next(int i) {if (i<n) return i+1;else return 1;}
inline double inv(double m) {if (m==0) return inf;else if (m==inf) return 0;else return -1.0/m;}
inline double d(str a, str b, double m) {if (m==0) return fabs(a.y-b.y);else if (m==inf) return fabs(a.x-b.x);double n=b.y-m*b.x,h;str c;c.x=b.x+1;c.y=c.x*m+n;h=det(a,b,c)/dist(b, c);if (h < 0) return -h;else return h;}

void get_hull()
{
	int p=1,i,m;
	for (i=2;i<=n;++i)
		if (a[i].x<a[p].x||(a[i].x==a[p].x&&a[i].y<a[p].y))
			p=i;
	swap(a[1],a[p]);
	sort(a+2,a+n+1,cmp);
	hull[1]=a[1];hull[2]=a[2];m =2;
	for (i=3;i<=n;++i)
	{
		if (!(det(a[i],hull[m],hull[m-1])==0&&min(hull[m].x,hull[m-1].x)<=a[i].x&&a[i].x<=max(hull[m].x,hull[m-1].x)))
        {
            ++m;
            hull[m]=a[i];
        }
		while (m>2&&det(hull[m-2],hull[m-1],hull[m])<=0)
		{
    		swap(hull[m-1],hull[m]);
			--m;
		}
	}
	n=m;
	for (i=1;i<=n;++i)
		a[i]=hull[i];
}

int main()
{
    double m,sol=inf;
    int i,j,l,u,r,nxt;
	freopen("rubarba.in","r",stdin);
	freopen("rubarba.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
		scanf("%lf%lf",&a[i].x,&a[i].y);
	get_hull();
	for (i=1;i<=n;++i)
	{
    	nxt=next(i);
		if (a[i].x==a[nxt].x)
			m=inf;
		else
			m=1.0*(a[nxt].y-a[i].y)/(a[nxt].x-a[i].x);
		l=i;
		u=i;
		r=i;
		for (j=next(i);j!=i;j=next(j))
		{
			if (d(a[j],a[i],m)>d(a[u],a[i],m))
				u=j;
        	if (d(a[j],a[i],inv(m))>d(a[l],a[i],inv(m)))
				l=j;
		}
		for (j=next(l);j!=l;j=next(j))
			if (d(a[j],a[l],inv(m))>d(a[r],a[l],inv(m)))
				r=j;

		double current_sol=d(a[u],a[i],m)*d(a[l],a[r],inv(m));
		if (current_sol<sol)
			sol=current_sol;
	}
	printf("%.2lf\n",sol);
	return 0;
}