Cod sursa(job #936927)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 9 aprilie 2013 04:31:20
Problema Rubarba Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.33 kb
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <list>
#include <algorithm>
#include <math.h>
#include <assert.h>
using namespace std;


const string file = "rubarba";

const string infile = file + ".in";
const string outfile = file + ".out";


struct Point
{
	int x;
	int y;
};


int N;

vector<Point> points;
vector<int> convexHull;
double minArea;

void citire()
{

	ifstream fin(infile.c_str());

	fin >> N;

	points.resize(N);

	int minI = 0;

	for(int i = 0; i < N; i++)
	{
		int x, y;
		fin >> x >> y;

		points[i].x = x;
		points[i].y = y;

		if((points[i].x < points[minI].x) || (points[i].x == points[minI].x && points[i].y < points[minI].y))
		{
			minI = i;
		}
	}

	swap(points[0], points[minI]);

	fin.close();
}


bool pSort(const Point& a, const Point& b)
{
	double val1 = (double)((a.y - points[0].y ))/(double)((a.x - points[0].x));
	double val2 = (double)((b.y - points[0].y ))/(double)((b.x - points[0].x));

	return val1 < val2;
}


long long CrossProduct(int a, int b, int c)
{
	Point & pA = points[a];
	Point & pB = points[b];
	Point & pC = points[c];

	long long result = 1LL *(pB.x - pA.x)*(pC.y - pA.y) - 1LL *(pB.y - pA.y)*(pC.x - pA.x);

	return result;
}

void GrahamScan()
{
	sort(points.begin() + 1, points.end(), pSort);
	convexHull.reserve(N);

	for(int i = 0; i < N; i++)
	{

		while(convexHull.size() > 0 && points[convexHull[convexHull.size() - 1]].x == points[i].x && points[convexHull[convexHull.size() - 1]].y == points[i].y)
		{
			convexHull.pop_back();
		}

		while(convexHull.size() >= 2 && CrossProduct(convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], i) <= 0)
		{
			convexHull.pop_back();
		}
		convexHull.push_back(i);
	}

}


struct PointD
{
	double x;
	double y;

	PointD()
	{

	}

	PointD(double x, double y)
	{
		this->x = x;
		this->y = y;
	}
};

double ProdusScalar(PointD& p1, PointD& p2)
{
	return p1.x * p2.x + p1.y * p2.y;
}

double Norma(PointD& p)
{
	return sqrt(p.x * p.x + p.y * p.y);
}

PointD Translate(PointD& p1, PointD& p2)
{
	return PointD(p2.x - p1.x, p2.y - p1.y);
}

void RotateClockwise(PointD& p, double sine, double cosine)
{
	double x = p.x;
	double y = p.y;
	p.x = x * cosine + y * sine;
	p.y =  - x * sine + y * cosine;
}


int Next(int i)
{
	return i == 0 ? convexHull.size() - 1 : i - 1;
}

void RotatingCallipers()
{

	int xMin = 0;
	int xMax = 0;
	int yMin = 0;
	int yMax = 0;

	for(unsigned int i = 0; i < convexHull.size(); i++)
	{
		int currentPoint = i;

		xMin = points[convexHull[currentPoint]].x < points[convexHull[xMin]].x ? currentPoint : xMin;
		xMax = points[convexHull[currentPoint]].x > points[convexHull[xMax]].x ? currentPoint : xMax; 

		yMin = points[convexHull[currentPoint]].y < points[convexHull[yMin]].y ? currentPoint : yMin;
		yMax = points[convexHull[currentPoint]].y > points[convexHull[yMax]].y ? currentPoint : yMax;

	}

	double dXdif = (points[convexHull[xMax]].x - points[convexHull[xMin]].x);
	double dYdif = (points[convexHull[yMax]].y - points[convexHull[yMin]].y);
	minArea = dXdif * dYdif;

	double rotCos = 1;
	double rotSin = 0;

	PointD p[4];
	p[0] = PointD(0, 1);
	p[1] = PointD(0, -1);
	p[2] = PointD(-1, 0);
	p[3] = PointD(1, 0);

	int l[4];
	l[0] = xMin;
	l[1] = xMax;
	l[2] = yMin;
	l[3] = yMax;

	double currentCos[4];

	while(rotCos > 0)
	{
		double cosine = -1;

		for(int i = 0; i < 4; i++)
		{
			int current = convexHull[l[i]];
			int next = convexHull[Next(l[i])];

			PointD c(points[current].x, points[current].y);
			PointD n(points[next].x, points[next].y);

			PointD translated = Translate(c, n);

			currentCos[i] = ProdusScalar(p[i], translated) / Norma(translated);
			cosine = max(cosine, currentCos[i]);

		}

		double sine = sqrt(1 - cosine * cosine);

		for(int i = 0; i < 4; i++)
		{
			if(currentCos[i] == cosine)
			{
				l[i] = Next(l[i]);
			}

			RotateClockwise(p[i], sine, cosine);
		}

		double newC = rotCos * cosine - rotSin * sine; //cos(a+b)
		double newS = rotSin * cosine + rotCos * sine; //sin(a+b)

		rotCos = newC;
		rotSin = newS;

		double arie = 0;

		if(p[0].x  == 0 || p[0].y == 0)
		{

			xMin = xMax = yMin = yMax = l[0];

			for(int i = 1; i < 4; i++)
			{
				int currentPoint = l[i];
				xMin = points[convexHull[currentPoint]].x < points[convexHull[xMin]].x ? currentPoint : xMin;
				xMax = points[convexHull[currentPoint]].x > points[convexHull[xMax]].x ? currentPoint : xMax; 

				yMin = points[convexHull[currentPoint]].y < points[convexHull[yMin]].y ? currentPoint : yMin;
				yMax = points[convexHull[currentPoint]].y > points[convexHull[yMax]].y ? currentPoint : yMax;
			}
			
			double dXdif = (points[convexHull[xMax]].x - points[convexHull[xMin]].x);
			double dYdif = (points[convexHull[yMax]].y - points[convexHull[yMin]].y);

			arie = dXdif * dYdif;
		}
		else
		{
			double slopes[4];
			double constants[4];
			for(int i = 0; i < 4; i++)
			{
				slopes[i] = p[i].y/ p[i].x;
			}

			for(int i = 0; i < 4; i++)
			{
				constants[i] = 1.0*points[convexHull[l[i]]].y - slopes[i] * points[convexHull[l[i]]].x;
			}
			
			double xs[4];
			double ys[4];

			xs[0] = (constants[3] - constants[0]) / (slopes[0] - slopes[3]);
			ys[0] = xs[0] * slopes[0] + constants[0];

			xs[1] = (constants[3] - constants[1]) / (slopes[1] - slopes[3]);
			ys[1] = xs[1] * slopes[1] + constants[1];

			xs[2] = (constants[2] - constants[0]) / (slopes[0] - slopes[2]);
			ys[2] = xs[2] * slopes[0] + constants[0];

			double deltaXAB = xs[0] - xs[1];
			double deltaYAB = ys[0] - ys[1];

			double deltaXBC = xs[0] - xs[2];
			double deltaYBC = ys[0] - ys[2];

			double lengthAB = sqrt((deltaXAB * deltaXAB) + (deltaYAB * deltaYAB));
			double lengthBC = sqrt((deltaXBC * deltaXBC) + (deltaYBC * deltaYBC));

			arie =  lengthAB * lengthBC;


		}

		minArea = min(arie, minArea);

	}

}


void solve()
{
	GrahamScan();
	RotatingCallipers();
}

void afisare()
{
	ofstream fout(outfile.c_str());

	fout << fixed << setprecision(2) << minArea << "\n";

	fout.close();
}


int main()
{
	citire();
	solve();
	afisare();
}