Cod sursa(job #3345010)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 7 martie 2026 13:56:25
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.16 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());
	}
};

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);
}

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

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

int32_t GetNextInd(int32_t ind) {
	++ind;
	if(ind == hullSize)
		ind = 0;
	return ind;
}
void GetMaxInd(int32_t& ind, double& val, double(*func)(Vector point, Vector l1, Vector l2), Vector l1, Vector l2) {
	ind = 0;
	val = func(hull[0], l1, l2);
	for(int32_t i = 1; i != hullSize; ++i) {
		double currVal = func(hull[i], l1, l2);
		if(currVal > val) {
			ind = i;
			val = currVal;
		}
	}
}
void GetNextMaxInd(int32_t& ind, double& val, double(*func)(Vector point, Vector l1, Vector l2), Vector l1, Vector l2) {
	val = func(hull[ind], l1, l2);
	while(true) {
		int32_t nextInd = GetNextInd(ind);
		double nextVal = func(hull[nextInd], l1, l2);
		if(nextVal <= val)
			break;
		
		ind = nextInd;
		val = nextVal;
	}
}

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, upInd, rightInd;
	double leftDist, upDist, rightDist;
	double len = (hull[1] - hull[0]).Magnitude();

	GetMaxInd(leftInd, leftDist, GetProjectionLen, hull[1], hull[0]);
	GetMaxInd(upInd, upDist, GetPointLineDist, hull[0], hull[1]);
	GetMaxInd(rightInd, rightDist, GetProjectionLen, hull[0], hull[1]);

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

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

		GetNextMaxInd(leftInd, leftDist, GetProjectionLen, l2, l1);
		GetNextMaxInd(upInd, upDist, GetPointLineDist, l1, l2);
		GetNextMaxInd(rightInd, rightDist, GetProjectionLen, l1, l2);

		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;
}