Cod sursa(job #1244636)

Utilizator vladrochianVlad Rochian vladrochian Data 17 octombrie 2014 21:49:09
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.86 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;

const int kMaxPoints = 100005;

int N, polygon_size, pu, ps1, ps2;
double du, ds1, ds2, min_area;
bool su, ss1, ss2;
struct Point {
	double x, y;
	Point() {
		x = y = 0;
	}
	Point(double x, double y) {
		this->x = x;
		this->y = y;
	}
} p[kMaxPoints];
struct Line {
	double a, b, c;
	Line() {
		a = b = c = 0;
	}
	Line(double a, double b, double c) {
		this->a = a;
		this->b = b;
		this->c = c;
	}
	Line(const Point &p1, const Point &p2) {
		a = p2.y - p1.y;
		b = p1.x - p2.x;
		c = a * p1.x + b * p1.y;
	}
} base, perpendicular;
vector<int> convex_hull;

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

inline Point& Vertex(int i) {
	return p[convex_hull[i]];
}

double Area(const Point &p1, const Point &p2, const Point &p3) {
	return p1.x * p2.y
	     + p2.x * p3.y
	     + p3.x * p1.y
	     - p1.y * p2.x
	     - p2.y * p3.x
	     - p3.y * p1.x;
}

bool Compare(const Point &p1, const Point &p2) {
	return Area(p[0], p1, p2) > 0.0;
}

void Read() {
	fin >> N;
	for (int i = 0; i < N; ++i) {
		fin >> p[i].x >> p[i].y;
		if (p[i].x < p[0].x)
			swap(p[0], p[i]);
	}
	sort(p + 1, p + N, Compare);
}

void BuildConvexHull() {
	convex_hull.push_back(0);
	for (int i = 1; i < N; ++i) {
		while (convex_hull.size() > 1)
			if (Area(Vertex(convex_hull.size() - 2),
			         Vertex(convex_hull.size() - 1),
			         p[i]) > 0)
				break;
			else
				convex_hull.pop_back();
		convex_hull.push_back(i);
	}
	polygon_size = convex_hull.size();
	convex_hull.push_back(0);
}

Line PerpendicularBisector(const Point &p1, const Point &p2) {
	Point mid((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
	Line ln(p1, p2);
	double a, b, c;
	a = ln.b;
	b = -ln.a;
	c = a * mid.x + b * mid.y;
	return Line(a, b, c);
}

bool UpdateDist(double &d, double val, bool sign) {
	if (sign) {
		if (val < d) {
			d = val;
			return true;
		}
	} else {
		if (val > d) {
			d = val;
			return true;
		}
	}
	return false;
}

double Distance(const Point &p, const Line &l) {
	return (l.a * p.x + l.b * p.y - l.c) / sqrt(l.a * l.a + l.b * l.b);
}

void BuildRectangle() {
	base = Line(Vertex(0), Vertex(1));
	perpendicular = PerpendicularBisector(Vertex(0), Vertex(1));
	pu = 2;
	ps1 = 0;
	ps2 = 1;
	du = Distance(Vertex(2), base);
	ds1 = Distance(Vertex(0), perpendicular);
	ds2 = Distance(Vertex(1), perpendicular);
	su = du < 0.0 ? true : false;
	ss1 = ds1 < 0.0 ? true : false;
	ss2 = ds2 < 0.0 ? true : false;
	for (int i = 0; i < polygon_size; ++i){
		if (UpdateDist(du, Distance(Vertex(i), base), su))
			pu = i;
		if (UpdateDist(ds1, Distance(Vertex(i), perpendicular), ss1))
			ps1 = i;
		if (UpdateDist(ds2, Distance(Vertex(i), perpendicular), ss2))
			ps2 = i;
	}
	min_area = abs((ds1 - ds2) * du);
}

void GetNextRectangle(int edge) {
	base = Line(Vertex(edge), Vertex(edge + 1));
	perpendicular = PerpendicularBisector(Vertex(edge), Vertex(edge + 1));
	du = Distance(Vertex(pu), base);
	ds1 = Distance(Vertex(ps1), perpendicular);
	ds2 = Distance(Vertex(ps2), perpendicular);
	int i;
	i = (pu + 1) % polygon_size;
	while (UpdateDist(du, Distance(Vertex(i), base), su)) {
		pu = i;
		i = (i + 1) % polygon_size;
	}
	i = (ps1 + 1) % polygon_size;
	while (UpdateDist(ds1, Distance(Vertex(i), perpendicular), ss1)) {
		ps1 = i;
		i = (i + 1) % polygon_size;
	}
	i = (ps2 + 1) % polygon_size;
	while (UpdateDist(ds2, Distance(Vertex(i), perpendicular), ss2)) {
		ps2 = i;
		i = (i + 1) % polygon_size;
	}
	double new_area = abs((ds1 - ds2) * du);
	min_area = min(min_area, new_area);
}

int main() {
	Read();
	BuildConvexHull();
	BuildRectangle();
	for (int i = 1; i < polygon_size; ++i)
		GetNextRectangle(i);
	fout << setprecision(2) << fixed << min_area << "\n";
	return 0;
}