Cod sursa(job #3344931)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 6 martie 2026 19:05:50
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.54 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdint.h>
#include <algorithm>
#include <math.h>

const int32_t MAX_N = 100000;

struct Vector {
	int32_t x, y;

	Vector operator-(const Vector& other) const {
		return { x - other.x, y - other.y };
	}
	bool operator==(const Vector& other) const {
		return x == other.x && y == other.y;
	}

	int64_t Dot(const Vector& other) const {
		return (int64_t)x * other.x + (int64_t)y * other.y;
	}
	int64_t SqrMagnitude() const {
		return (int64_t)x * x + (int64_t)y * y;
	}
	double Magnitude() const {
		return sqrt(SqrMagnitude());
	}
};

int32_t n;
Vector points[MAX_N], center;
Vector hull[MAX_N]; int32_t hullSize = 0;
double res;

double min(double x, double y) {
	return (x < y) ? x : y;
}
int64_t GetSignedArea(Vector p1, Vector p2) {
	return (int64_t)p1.x * p2.y - (int64_t)p1.y * p2.x;
}
int64_t GetSignedArea(Vector p1, Vector p2, Vector p3) {
	return (int64_t)p1.x * p2.y + (int64_t)p2.x * p3.y + (int64_t)p3.x * p1.y - (int64_t)p1.y * p2.x - (int64_t)p2.y * p3.x - (int64_t)p3.y * p1.x;
}
double GetProjectionLen(Vector point, Vector l1, Vector l2) {
	Vector line = l2 - l1;
	Vector relPos = point - l2;
	return line.Dot(relPos) / line.Magnitude();
}
double GetPointLineDist(Vector point, Vector l1, Vector l2) {
	if(point == l1 || point == l2)
		return 0.0;

	int64_t sqrDist = (point - l2).SqrMagnitude();
	double proj = GetProjectionLen(point, l1, l2);
	return sqrt(sqrDist - proj * proj);
}

bool CompPoints(const Vector& p1, const Vector& p2) {
	int64_t area = GetSignedArea(p1, p2);
	if(area)
		return area > 0;
	return p1.SqrMagnitude() < p2.SqrMagnitude();
}

void ReadPoints(std::istream& fin) {
	fin >> n;
	for(int32_t i = 0; i != n; ++i)
		fin >> points[i].x >> points[i].y;
}
void SortPoints() {
	center = points[0];
	for(int32_t i = 1; i != n; ++i) {
		if(points[i].y < center.y || (points[i].y == center.y && points[i].x < center.x))
			center = points[i];
	}
	for(int32_t i = 0; i != n; ++i)
		points[i] = points[i] - center;
	
	std::sort(points, points + n, CompPoints);
}
void GenerateHull() {
	hullSize = 1;
	hull[0] = points[0];

	for(int32_t i = 1; i != n; ++i) {
		while(hullSize >= 2 && GetSignedArea(hull[hullSize - 2], hull[hullSize - 1], points[i]) <= 0)
			--hullSize;
		hull[hullSize++] = points[i];
	}
}
void Solve() {
	if(hullSize <= 2) {
		res = 0.0;
		return;
	}

	int32_t leftInd = 0, upInd = 0, rightInd = 1;
	double leftDist = 0.0, upDist = 0.0, rightDist = 0.0;
	double len = (hull[1] - hull[0]).Magnitude();

	for(int32_t i = 2; i != hullSize; ++i) {
		double dist = GetProjectionLen(hull[i], hull[1], hull[0]);
		if(dist > leftDist) {
			leftDist = dist;
			leftInd = i;
		}
	}
	for(int32_t i = 2; i != hullSize; ++i) {
		double dist = GetPointLineDist(hull[i], hull[0], hull[1]);
		if(dist > upDist) {
			upDist = dist;
			upInd = i;
		}
	}
	for(int32_t i = 2; i != hullSize; ++i) {
		double dist = GetProjectionLen(hull[i], hull[0], hull[1]);
		if(dist > rightDist) {
			rightDist = dist;
			rightInd = i;
		}
	}

	res = (len + leftDist + rightDist) * upDist;

	for(int32_t i = 1; i != hullSize; ++i) {
		int32_t nextInd = i + 1;
		if(nextInd == hullSize)
			nextInd = 0;
		Vector l1 = hull[i], l2 = hull[nextInd];
		len = (l2 - l1).Magnitude();

		leftDist = GetProjectionLen(hull[leftInd], l2, l1);
		while(true) {
			nextInd = leftInd + 1;
			if(nextInd == hullSize)
				nextInd = 0;

			double nextDist = GetProjectionLen(hull[nextInd], l2, l1);
			if(nextDist <= leftDist)
				break;
			
			leftDist = nextDist;
			leftInd = nextInd;
		}

		upDist = GetPointLineDist(hull[upInd], l1, l2);
		while(true) {
			nextInd = upInd + 1;
			if(nextInd == hullSize)
				nextInd = 0;

			double nextDist = GetPointLineDist(hull[nextInd], l1, l2);
			if(nextDist <= upDist)
				break;
			
			upDist = nextDist;
			upInd = nextInd;
		}

		rightDist = GetProjectionLen(hull[rightInd], l1, l2);
		while(true) {
			nextInd = rightInd + 1;
			if(nextInd == hullSize)
				nextInd = 0;

			double nextDist = GetProjectionLen(hull[nextInd], l1, l2);
			if(nextDist <= rightDist)
				break;
			
			rightDist = nextDist;
			rightInd = nextInd;
		}

		res = min(res, (len + leftDist + rightDist) * upDist);
	}
}

int main() {
	std::ifstream fin("rubarba.in");
	std::ofstream fout("rubarba.out");

	ReadPoints(fin);
	SortPoints();
	GenerateHull();
	Solve();
	fout << std::fixed << std::setprecision(2) << res << '\n';

	fin.close();
	fout.close();

	return 0;
}