Pagini recente » Cod sursa (job #2292563) | Cod sursa (job #99271) | Cod sursa (job #1964853) | Cod sursa (job #1369008) | Cod sursa (job #937158)
Cod sursa(job #937158)
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <list>
#include <algorithm>
#include <math.h>
#include <assert.h>
using namespace std;
const string file = "rubarba";
const string infile = file + ".in";
const string outfile = file + ".out";
struct Point
{
int x;
int y;
};
int N;
vector<Point> points;
vector<int> convexHull;
double minArea;
void citire()
{
ifstream fin(infile.c_str());
fin >> N;
points.resize(N);
int minI = 0;
for(int i = 0; i < N; i++)
{
int x, y;
fin >> x >> y;
points[i].x = x;
points[i].y = y;
if((points[i].x < points[minI].x) || (points[i].x == points[minI].x && points[i].y < points[minI].y))
{
minI = i;
}
}
swap(points[0], points[minI]);
fin.close();
}
bool pSort(const Point& a, const Point& b)
{
double val1 = (double)((a.y - points[0].y ))/(double)((a.x - points[0].x));
double val2 = (double)((b.y - points[0].y ))/(double)((b.x - points[0].x));
return val1 < val2;
}
long long CrossProduct(int a, int b, int c)
{
Point & pA = points[a];
Point & pB = points[b];
Point & pC = points[c];
long long result = 1LL *(pB.x - pA.x)*(pC.y - pA.y) - 1LL *(pB.y - pA.y)*(pC.x - pA.x);
return result;
}
void GrahamScan()
{
sort(points.begin() + 1, points.end(), pSort);
convexHull.reserve(N);
for(int i = 0; i < N; i++)
{
while(convexHull.size() >= 2 && CrossProduct(convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], i) <= 0)
{
long long cross = CrossProduct(convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], i);
convexHull.pop_back();
}
convexHull.push_back(i);
}
}
struct PointD
{
double x;
double y;
PointD()
{
}
PointD(double x, double y)
{
this->x = x;
this->y = y;
}
};
struct LineD
{
LineD()
{
}
LineD(const Point& p1, const Point& p2)
{
this->slope = 1.0 *(p2.y - p1.y) / (p2.x - p1.x);
this->c = p1.y - p1.x * slope;
}
LineD(const Point& p1, double slope)
{
this->c = p1.y - p1.x * slope;
this->slope = slope;
}
double slope;
double c;
};
PointD GetIntersection(const LineD& l1, const LineD& l2)
{
double px = 0;
double py = 0;
px = (l1.c - l2.c)/(l2.slope - l1.slope);
py = l1.slope * px + l1.c;
return PointD(px, py);
}
double ProdusScalar(const PointD& p1, const PointD& p2)
{
return p1.x * p2.x + p1.y * p2.y;
}
double Norma(const PointD& p)
{
return sqrt(p.x * p.x + p.y * p.y);
}
PointD Translate(const PointD& p1, const PointD& p2)
{
return PointD(p2.x - p1.x, p2.y - p1.y);
}
void RotateClockwise(PointD& p, double sine, double cosine)
{
double x = p.x;
double y = p.y;
p.x = x * cosine + y * sine;
p.y = - x * sine + y * cosine;
}
int Next(int i)
{
return i == 0 ? convexHull.size() - 1 : i - 1;
}
void RotatingCallipers()
{
int xMin = 0;
int xMax = 0;
int yMin = 0;
int yMax = 0;
for(unsigned int i = 0; i < convexHull.size(); i++)
{
int currentPoint = i;
xMin = points[convexHull[currentPoint]].x < points[convexHull[xMin]].x ? currentPoint : xMin;
xMax = points[convexHull[currentPoint]].x > points[convexHull[xMax]].x ? currentPoint : xMax;
yMin = points[convexHull[currentPoint]].y < points[convexHull[yMin]].y ? currentPoint : yMin;
yMax = points[convexHull[currentPoint]].y > points[convexHull[yMax]].y ? currentPoint : yMax;
}
double dXdif = (points[convexHull[xMax]].x - points[convexHull[xMin]].x);
double dYdif = (points[convexHull[yMax]].y - points[convexHull[yMin]].y);
minArea = dXdif * dYdif;
double rotCos = 1;
double rotSin = 0;
PointD p[4];
p[0] = PointD(0, 1);
p[1] = PointD(0, -1);
p[2] = PointD(-1, 0);
p[3] = PointD(1, 0);
int l[4];
l[0] = xMin;
l[1] = xMax;
l[2] = yMin;
l[3] = yMax;
double currentCos[4];
while(rotCos > 0)
{
double cosine = -1;
for(int i = 0; i < 4; i++)
{
int current = convexHull[l[i]];
int next = convexHull[Next(l[i])];
PointD c(points[current].x, points[current].y);
PointD n(points[next].x, points[next].y);
PointD translated = Translate(c, n);
currentCos[i] = ProdusScalar(p[i], translated) / Norma(translated);
cosine = max(cosine, currentCos[i]);
}
double sine = sqrt(1 - cosine * cosine);
int lineP;
int linePindex;
for(int i = 0; i < 4; i++)
{
if(currentCos[i] == cosine)
{
lineP = convexHull[l[i]];
l[i] = Next(l[i]);
linePindex = i;
}
RotateClockwise(p[i], sine, cosine);
}
double newC = rotCos * cosine - rotSin * sine; //cos(a+b)
double newS = rotSin * cosine + rotCos * sine; //sin(a+b)
rotCos = newC;
rotSin = newS;
long double slopes[4];
Point &lineP1 = points[convexHull[l[linePindex]]];
Point &lineP2 = points[lineP];
if(lineP2.y == lineP1.y || lineP2.x == lineP1.x)
continue;
double slope1 = 1.0*(lineP2.y - lineP1.y) / (lineP2.x - lineP1.x);;
double slope2 = 1.0*(-1)/slope1;
if(linePindex < 2)
{
slopes[0] = slopes[1] = slope1;
slopes[2] = slopes[3] = slope2;
}
else
{
slopes[2] = slopes[3] = slope1;
slopes[0] = slopes[1] = slope2;
}
LineD lines[4];
for(int i = 0; i < 4; i++)
{
lines[i] = LineD(points[convexHull[l[i]]], slopes[i]);
}
PointD A = GetIntersection(lines[3], lines[0]);
PointD B = GetIntersection(lines[3], lines[1]);
PointD C = GetIntersection(lines[2], lines[0]);
PointD AB = Translate(B, A);
PointD AC = Translate(C, A);
double area = Norma(AB) * Norma(AC);
cout << fixed << setprecision(2) << area << "\n";
minArea = min(area, minArea);
}
}
void solve()
{
GrahamScan();
RotatingCallipers();
}
void afisare()
{
ofstream fout(outfile.c_str());
fout << fixed << setprecision(2) << minArea << "\n";
fout.close();
}
int main()
{
citire();
solve();
afisare();
}