Cod sursa(job #680077)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 14 februarie 2012 05:54:11
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 3.85 kb
#define _USE_MATH_DEFINES
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#define MAXN 1001

using namespace std;

struct Point
{
	Point() :
		x(.0f),
		y(.0f),
		moveDist(.0f)
	{}
	
	Point(const long double xx, const long double yy, const long double d) :
		x(xx),
		y(yy),
		moveDist(d)
	{}
	
	bool operator < (const Point& p) const
	{
		return this->x < p.x || (this->x==p.x && this->y<p.y);
	}
	
	long double x, y;
	long double moveDist;
};

inline long double CrossProduct(const Point& O, const Point& p1, const Point& p2)
{
	return (p1.x - O.x)*(p2.y - O.y) - (p1.y - O.y)*(p2.x - O.x);
}

int ConvexHull(const vector<Point>& vPoints, vector<Point>& vHull)
{
	int n = vPoints.size(), k=0;
	vHull.resize(n+2);
	
	for (int i=0; i<n; ++i)
	{
		while (k>=2 && CrossProduct(vHull[k-2], vHull[k-1], vPoints[i])<0)
			k--;
		vHull[k++] = vPoints[i];
	}
	
	int start = k+1;
	for (int i=n-2; i>=0; --i)
	{
		while (k>=start && CrossProduct(vHull[k-2], vHull[k-1], vPoints[i])<0)
			k--;
		vHull[k++] = vPoints[i];
	}
	
	vHull.resize(k);
	return k;
}

inline long double GetAddedArea(const Point& p1, const Point& p2, const long double dist)
{
	const long double base = static_cast<long double>(sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)));
	return (base*dist)/2;
}

int main()
{
	int n;
	vector<Point> vPoints;
	vector<Point> vHull;
	long double bst[MAXN];
	fstream fin("mosia.in", fstream::in);
	fstream fout("mosia.out", fstream::out);
	
	fin >> n;
	//cout << n << "\n";
	
	for (int i=0; i<n; ++i)
	{
		int x, y, d;
		fin >> x >> y >> d;
		
		vPoints.push_back(Point(x, y, d));
	}
	
	sort(vPoints.begin(), vPoints.end());
	
	ConvexHull(vPoints, vHull);
	
	/*for (int i=0; i<n; ++i)
	{
		cout << vHull[i].x << " " << vHull[i].y << " " << vHull[i].moveDist << "\n";
	}*/
	
	// case 0: only 3 points
	const long double areaInc0 = GetAddedArea(vHull[n-1], vHull[1], vHull[0].moveDist);
	if (3 == n)
	{
		const long double areaInc1 = GetAddedArea(vHull[2], vHull[0], vHull[1].moveDist);
		const long double areaInc2 = GetAddedArea(vHull[0], vHull[1], vHull[2].moveDist);
		
		const long double maxAreaInc = max(areaInc0, max(areaInc1, areaInc2));
		
		fout.precision(25);
		fout << fixed << maxAreaInc << "\n";
	}
	
	// case 1
	bool useFirst = false;
	bst[0] = GetAddedArea(vHull[n-1], vHull[1], vHull[0].moveDist);
	bst[1] = GetAddedArea(vHull[0], vHull[2], vHull[1].moveDist);
	
	for (int i=2; i<n-1; ++i)
	{
		const long double areaIncI = GetAddedArea(vHull[i-1], vHull[i+1], vHull[i].moveDist);
		if (bst[i-2] + areaIncI >= bst[i-1])
		{
			bst[i] = bst[i-2] + areaIncI;
			if (i-2 == 0)
			{
				useFirst = true;
			}
		}
		else
		{
			bst[i] = bst[i-1];
		}
	}
	
	if (useFirst == true)
	{
		bst[n-1] = bst[n-2];
	}
	else
	{
		const long double areaIncN = GetAddedArea(vHull[0], vHull[n-2], vHull[n-1].moveDist);
		bst[n-1] = max(bst[n-3] + areaIncN, bst[n-2]);
	}
	
	long double bestArea =  bst[n-1];
	
	//cout << bestArea << "\n";
	
	bst[1] = GetAddedArea(vHull[0], vHull[2], vHull[1].moveDist);
	bst[2] = GetAddedArea(vHull[1], vHull[3], vHull[2].moveDist);
	
	// case 2
	for (int i=3; i<n-1; ++i)
	{
		const long double areaIncI = GetAddedArea(vHull[i-1], vHull[i+1], vHull[i].moveDist);
		if (bst[i-2] + areaIncI >= bst[i-1])
		{
			bst[i] = bst[i-2] + areaIncI;
		}
		else
		{
			bst[i] = bst[i-1];
		}
	}
	
	const long double areaIncN = GetAddedArea(vHull[0], vHull[n-2], vHull[n-1].moveDist);
	if (bst[n-3] + areaIncN >= bst[n-2])
	{
		bst[n-1] = bst[n-3] + areaIncN;
	}
	else
	{
		bst[n-1] = bst[n-2] + areaInc0;
	}
	
	//cout << bst[n-1] << "\n";
	
	bestArea = max(bestArea, bst[n-1]);

	fout.precision(25);
	fout << fixed << bestArea << "\n";
	
	fin.close();
	fout.close();
	return 0;
}