Pagini recente » Cod sursa (job #984011) | Cod sursa (job #1753207) | Cod sursa (job #877325) | Cod sursa (job #821203) | Cod sursa (job #3344931)
#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;
}