Cod sursa(job #2924463)

Utilizator lolismekAlex Jerpelea lolismek Data 2 octombrie 2022 22:08:52
Problema Rubarba Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.76 kb
//TODO: pisica Ferguson trebuie sa repare bug-urile
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

namespace Geometry{
	struct Point{
		double x, y;
	};

	struct Segment{
		Point p1, p2;
	};
 
	double dist(Point p1, Point p2){
		double dx = p1.x - p2.x, dy = p1.y - p2.y;
		return sqrt(dx * dx + dy * dy);
	}
 
	double area(Point p1, Point p2, Point p3){
		return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
	}
 
	double polygonArea(vector <Point> v){
		double A = 0;
		int n = (int)v.size();
		for(int i = 0; i < n; i++)
			A += area(v[i], v[(i + 1) % n], {0, 0});
		return A / 2;
	}
 
	double distToSeg(Point p, Segment s){ // not absolute
		return area(p, s.p1, s.p2) / dist(s.p1, s.p2);
	}

	Segment calcPerp(Segment s){
		Point M = {(s.p1.x + s.p2.x) / 2, (s.p1.y + s.p2.y) / 2};

		if(s.p1.y > s.p2.y)
			swap(s.p1, s.p2);

		double dx = abs(s.p1.x - M.x), dy = abs(s.p1.y - M.y);

		if(s.p1.y < s.p2.y)
			dy = -dy;

		return {M, {M.x + dx, M.y + dy}};
	}

	bool cmp(Point a, Point b){
		if(a.x == b.x)
			return a.y < b.y;
		return a.x < b.x;
	}
 
	vector <Point> convexHull(vector <Point> v){
		int n = (int)v.size();
		sort(v.begin(), v.end(), cmp);
 
		vector <Point> up, down;
		up.push_back(v[1]);
		down.push_back(v[1]);
 
		for(int i = 1; i < n; i++){
			while((int)up.size() > 1 && area(up[(int)up.size() - 2], up[(int)up.size() - 1], v[i]) <= 0)
				up.pop_back();
			up.push_back(v[i]);
			while((int)down.size() > 1 && area(down[(int)down.size() - 2], down[(int)down.size() - 1], v[i]) >= 0)
				down.pop_back();
			down.push_back(v[i]);
		}
 
		vector <Point> CH = up;
		for(int i = (int)down.size() - 2; i >= 1; i--)
			CH.push_back(down[i]);
 
		reverse(CH.begin(), CH.end());
 
		return CH;
	}		
}

const int N = 1e5, inf = 1e9;
vector <Geometry::Point> v;

int main(){

	int n;
	fin >> n;

	for(int i = 1; i <= n; i++){
		Geometry::Point point;
		fin >> point.x >> point.y;
		v.push_back(point);
	}

	v = Geometry::convexHull(v);

	int indS = 0, indD = 0, indF = 0;
	Geometry::Segment base = {v[0], v[1]};
	Geometry::Segment perp = Geometry::calcPerp(base);

	double maxDist, minDist;

	maxDist = 0;
	for(int i = 0; i < (int)v.size(); i++)
		if(abs(Geometry::distToSeg(v[i], base)) > maxDist)
			maxDist = abs(distToSeg(v[i], base)), indF = i;
	
	maxDist = 0, minDist = inf;
	for(int i = 0; i < (int)v.size(); i++){
		if(Geometry::distToSeg(v[i], perp) > maxDist)
			maxDist = Geometry::distToSeg(v[i], perp), indS = i;
		if(Geometry::distToSeg(v[i], perp) < minDist)
			minDist = Geometry::distToSeg(v[i], perp), indD = i;
	}

	double minArea = Geometry::distToSeg(v[indF], base) * (Geometry::distToSeg(v[indS], perp) + Geometry::distToSeg(v[indD], perp));
	for(int i = 1; i < n; i++){
		Geometry::Segment base = {v[i], v[(i + 1) % (int)v.size()]};
		Geometry::Segment perp = Geometry::calcPerp(base);
		while(abs(Geometry::distToSeg(v[(indS + 1) % (int)v.size()], perp)) > abs(Geometry::distToSeg(v[indS], perp)) || indS == (i + 1) % (int)v.size())
			indS = (indS + 1) % (int)v.size();
		while(abs(Geometry::distToSeg(v[(indD + 1) % (int)v.size()], perp)) < abs(Geometry::distToSeg(v[indD], perp)) || indD == i)
			indD = (indD + 1) % (int)v.size();
		while(abs(Geometry::distToSeg(v[(indF + 1) % (int)v.size()], base)) > abs(Geometry::distToSeg(v[indD], base)) || indF == (i + 1) % (int)v.size())
			indF = (indF + 1) % (int)v.size();

		minArea = min(minArea, abs(Geometry::distToSeg(v[indF], base)) * (abs(Geometry::distToSeg(v[indS], perp)) + abs(Geometry::distToSeg(v[indD], perp))));
	}

	fout << minArea << '\n';

	return 0;
}