Cod sursa(job #937339)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 10 aprilie 2013 03:14:06
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.8 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
{
	Point(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
	int x;
	int y;
};


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

long long CrossProduct(const Point& s, const Point& p1, const Point& p2)
{
	long long result = 1LL * (p1.x - s.x)*(p2.y - s.y) - 1LL * (p1.y - s.y) * (p2.x - s.x);
	return result;
}


Point Substract(const Point&a, const Point &b)
{
	int px = b.x - a.x;
	int py = b.y - a.y;

	return Point(px, py);
}

double Distance(const Point&a)
{
	
	return sqrt(double(a.x * a.x) + a.y * a.y);
}


bool SortPredicate(const Point& a, const Point& b)
{

	double val1 = 1.0*(a.y - points[0].y )/(1.0*a.x - points[0].x);
	double val2 = 1.0*(b.y - points[0].y )/(1.0*b.x - points[0].x);

	if(val1 < val2)
	{
		return true;
	}

	if(val1 > val2)
	{
		return false;
	}

	return Distance(Substract(a, points[0])) < Distance(Substract(b, points[0]));

	
}

void citire()
{
	ifstream fin(infile.c_str());

	fin >> N;
	points.reserve(N);
	int minI = 0;
	for(int i = 0 ; i < N; i++)
	{
		int x, y;
		fin >> x >> y;
		points.push_back(Point(x, y));

		if(points[minI].x > x)
		{
			minI = i;
		}
		else if(points[minI].x == x)
		{
			minI = points[minI].y > y ? i : minI;
		}

	}

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

	fin.close();
}

void GrahamScan()
{
	sort(points.begin() + 1, points.end(), SortPredicate);

	for(int i = 0; i < N; i++)
	{
		while(convexHull.size() >= 2 && CrossProduct(convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], points[i]) <= 0LL)
		{
			convexHull.pop_back();
		}

		convexHull.push_back(points[i]);
	}
	/*
	ofstream fout("convexHull.out");
	for(int i = 0; i < convexHull.size(); i++)
	{
		fout << convexHull[i].x << " " << convexHull[i].y << "\n";
	}
	fout.close();
	*/
}

struct PointD
{
	double x;
	double y;

	PointD()
	{

	}

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


struct LineD
{
	LineD()
	{

	}

	LineD(const Point& p1, const Point& p2)
	{
		this->slope = 1.0 *(p2.y - p1.y) / (p2.x - p1.x);
		this->c = p1.y - p1.x * slope;
	}

	LineD(const Point& p1, double slope)
	{
		this->c = p1.y - p1.x * slope;
		this->slope = slope;
	}

	double slope;
	double c;
};


PointD GetIntersection(const LineD& l1, const LineD& l2)
{
	double px = 0;
	double py = 0;

	px = (l1.c - l2.c)/(l2.slope - l1.slope);
	py = l1.slope * px + l1.c;

	return PointD(px, py);
}

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

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

PointD Translate(const PointD& p1, const 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()
{

	if(convexHull.size() <= 2)
	{
		minArea = 0;
		return;
	}

	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 = convexHull[currentPoint].x < convexHull[xMin].x ? currentPoint : xMin;
		xMax = convexHull[currentPoint].x > convexHull[xMax].x ? currentPoint : xMax; 

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

	}

	double dXdif = (convexHull[xMax].x - convexHull[xMin].x);
	double dYdif = (convexHull[yMax].y - 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 = l[i];
			int next = Next(l[i]);

			PointD c(convexHull[current].x, convexHull[current].y);
			PointD n(convexHull[next].x, convexHull[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);


		int lineP = 0;
		int linePindex = 0;
		for(int i = 0; i < 4; i++)
		{
			if(currentCos[i] == cosine)
			{
				lineP = l[i];
				l[i] = Next(l[i]);
				linePindex = 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;

		if(fabs(cosine - 1) < 0.01 || fabs(cosine) < 0.01)
			continue;

		long double slopes[4];

		Point &lineP1 = convexHull[l[linePindex]];
		Point &lineP2 = convexHull[lineP];

		if(lineP2.y == lineP1.y || lineP2.x == lineP1.x)
			continue;

		double slope1 = 1.0*((double)lineP2.y - (double)lineP1.y) / ((double)lineP2.x - (double)lineP1.x);;
		double slope2 = 1.0*(-1)/slope1;

		if(linePindex < 2)
		{
			slopes[0] = slopes[1] = slope1;
			slopes[2] = slopes[3] = slope2;
		}
		else
		{
			slopes[2] = slopes[3] = slope1;
			slopes[0] = slopes[1] = slope2;
		}

		LineD lines[4];

		for(int i = 0; i < 4; i++)
		{
			lines[i] = LineD(convexHull[l[i]], slopes[i]);
		}

		PointD A = GetIntersection(lines[3], lines[0]);
		PointD B = GetIntersection(lines[3], lines[1]);
		PointD C = GetIntersection(lines[2], lines[0]);

		PointD AB = Translate(B, A);
		PointD AC = Translate(C, A);

		double area = Norma(AB) * Norma(AC);


		cout << "NORMA(AB) =\t" << Norma(AB) << "\n";
		cout << "NORMA(AC) =\t" << Norma(AC) << "\n";

		cout << setprecision(8);
		cout << "A =\t" << A.x  << "\t" << A.y << "\n";
		cout << "B =\t" << B.x  << "\t" << B.y << "\n";
		cout << "C =\t" << C.x  << "\t" << C.y << "\n";

		cout << fixed << setprecision(2) << "AREA =\t" <<  area << "\n";  
		minArea = min(area, minArea);
		cout << "\n";
	}

}


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

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

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

	fout.close();
}


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