Cod sursa(job #1586300)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 31 ianuarie 2016 23:24:19
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
// Template v2
#define pb push_back
#include<bits/stdc++.h>
   
using namespace std;
   
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<double, double> PKK;
// primes less than 100
const int PRIM[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
const int dx[] = {-1, 0, 1, 0}; // ,1,1,-1,-1};
const int dy[] = {0, 1, 0, -1}; // ,1,-1,-1,1};
const int CMAX = 350;
const int NMAX = 100000;
const short INF16 = 32000;
const int INF = int(1e9);
const LL INF64 = LL(1e18);
const LD EPS = 1e-9, PI = acos(-1.0);

struct P{
	double x,y;
};

bool cmp(P l, P r)
{
	return (l.x<r.x || (l.x==r.x && l.y<r.y));
}

double orientation(P a, P b, P c) 
{
    /*
        orientation < 0 then counter-clockwise
        orientation = 0 then collinear
        orientation > 0 then clockwise
    */
    return 1.0*(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
int n,k,j,l,m;
LD a,b,g,d;
LD area=1.0*INF;
P A[NMAX];
P H[2*NMAX];

double angle(int i)
{
	double result = atan2(H[i].y-H[i+1].y,H[i].x-H[i+1].x)-atan2(H[i-1].y-H[i].y, H[i-1].x-H[i].x);
	cout<<result<<" -<";
	if(result<0)
	{
		result+=PI;
	}
	return result;
}

double perpdist(double x1, double y1, double x2, double y2, double s)
{
	double a,b,c;
	a=s;
	b=-1;
	c=y2-s*x2;
	return 1.0*(abs(a*x1+b*y1+c)/sqrt(a*a + b*b));
}

void hull()
{
	sort(A,A+n,cmp);
	int i,t;
	for(i=0, k=0; i<n; ++i)
	{
		while(k>=2 && orientation(H[k-2], H[k-1], A[i])<=0)
			k--;
		H[k++]=A[i];
	}
	for(i=n-2, t=k+1; i>=0; --i)
	{
		while(k>=t && orientation(H[k-2], H[k-1], A[i])<=0)
			k--;
		H[k++]=A[i];
	}
	k--;
	cout<<k<<"\n";
	for(int i=0; i<k/2+1; ++i)
	{
		swap(H[i], H[k-i]);
	}
}

bool read()
{
	if(!(cin>>n)) return 0;
	for(int i=0; i<n; ++i)
		cin>>A[i].x>>A[i].y;
	return 1;
}

void solve()
{
	hull();

	int i=0;
	P AUX[NMAX];
	while(H[i+1].y<H[i].y)
		i++;
	for(int j=i; j<k; ++j)
	{
		AUX[j-i]=H[j];
	}
	for(int j=0; j<i; ++j)
	{
		AUX[k-i+j]=H[j];
	}
	for(int i=0; i<k; ++i)
		H[i]=AUX[i], cout<<H[i].x<<" "<<H[i].y<<"\n";


	j=l=m=1;
	a=0;
	b=angle(1);
	g=d=b;
	LD d1,d2;
	
	for(int i=0; i<k; ++i)
	{
		if(i>=1)
			a+=angle(i%k);
		
		while(b<a+PI/2){
			j++;
			b+=angle(j%k);
		}
		
		while(g<a+PI){
			l++;
		 	g+=angle(l%k);
		}
		while(d<a+(3*PI)/2){
			m++;
			d+=angle(m%k);
		}
		
		if(H[(i+1)%k].x==H[i%k].x)
		{
			d1=abs(H[l%k].x-H[i%k].x);
			d2=abs(H[m%k].y-H[j%k].y);
		}
		else
			if(H[(i+1)%k].y==H[i%k].y)
			{
				d1=abs(H[l%k].x-H[i%k].x);
				d2=abs(H[m%k].y-H[j%k].y);
			}
			else
			{
				LD s=1.0*(H[(i+1)%k].y-H[i%k].y)/(H[(i+1)%k].x-H[i%k].x);
				cout<<i<<" this "<<s<<"\n";
				cout<<H[i%k].x<<" "<<H[i%k].y<<" "<<H[l%k].x<<" "<<H[l%k].y<<" "<<s<<"\n";
				cout<<H[j%k].x<<" "<<H[j%k].y<<" "<<H[m%k].x<<" "<<H[m%k].y<<" "<<-1.0/s<<" \n";
				d1=perpdist(H[i%k].x, H[i%k].y, H[l%k].x, H[l%k].y, s);
				d2=perpdist(H[j%k].x, H[j%k].y, H[m%k].x, H[m%k].y, -1.0/s);
			}
		cout<<d1*d2<<"\n";
		area=min(area, d1*d2);
		
		cout<<" \n";
	}
	
	cout<<area<<" \n";
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    assert(freopen("rubarba.in", "rt", stdin));

	cout<<setprecision(16);
	while(read()){
		solve();
	}
    return 0;
}