Pagini recente » Cod sursa (job #3196078) | Cod sursa (job #1228666) | Cod sursa (job #2133850) | Cod sursa (job #1942657) | Cod sursa (job #1358144)
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define pb push_back
#define infinite 100001
#define PI 3.14159265359
using namespace std;
ifstream fin("rubaba.in");
ofstream fout("rubaba.out");
typedef struct{
int id;
long double x;
long double y;
}Point;
typedef struct{
double angle;
Point P;
}C;
bool pointsort(Point A, Point B)
{
return (A.x<B.x||(A.x==B.x && A.y<B.y));
}
double ccw(Point O, Point A, Point B)
{
return (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x);
}
double angle(Point A, Point B)
{
if(B.x==A.x) return PI/2;
double r=atan((B.y-A.y)/(B.x-A.x));
return r<0?PI+r:r;
}
vector <Point> P;
C Caliper[5];
int n;
int main() {
fin>>n;
for(int i=0; i<n; ++i)
{
Point A;
fin>>A.x>>A.y;
P.pb(A);
}
sort(P.begin(), P.end(), pointsort);
vector <Point> H(n*2);
int k=0;
for(int i=0; i<n; ++i)
{
while(k>=2 && ccw(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
for(int i=n-2,t=k+1; i>=0; i--)
{
while(k>=t && ccw(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
k--;
for(int i=1; i<=k; ++i) // Dam id-uri pentru rotatii
H[i].id=i;
/*
for(int i=1; i<=k; ++i)
fout<<H[i].id<<" "<<H[i].x<<" "<<H[i].y<<"\n";
*/
Caliper[1].P.x=Caliper[3].P.y=infinite;
for(int i=1; i<=k; ++i){
if(H[i].x<Caliper[1].P.x) Caliper[1].P=H[i];
if(H[i].x>Caliper[2].P.x) Caliper[2].P=H[i];
if(H[i].y<Caliper[3].P.y) Caliper[3].P=H[i];
if(H[i].y>Caliper[4].P.y) Caliper[4].P=H[i];
}
double trotation=0;
double amin=infinite;
Caliper[1].angle=Caliper[2].angle=PI/2;
Caliper[3].angle=Caliper[4].angle=0;
double dist12 = sqrt(pow(Caliper[1].P.x-Caliper[2].P.x,2) + pow(Caliper[1].P.y-Caliper[2].P.y,2));
double dist34 = sqrt(pow(Caliper[3].P.x-Caliper[4].P.x,2) + pow(Caliper[3].P.y-Caliper[4].P.y,2));
double area=dist12*sin(abs(angle(Caliper[1].P, Caliper[2].P)-Caliper[1].angle))*dist34*sin(abs(angle(Caliper[3].P, Caliper[4].P)-Caliper[3].angle));
amin=area;
while(trotation<PI/2)
{
fout<<setprecision(2)<<fixed;
/*
fout<<"rotation: \n";
fout<<"Caliper 1: "<<Caliper[1].P.id<<" "<<Caliper[1].angle<<"\n";
fout<<"Caliper 2: "<<Caliper[2].P.id<<" "<<Caliper[2].angle<<"\n";
fout<<"Caliper 3: "<<Caliper[3].P.id<<" "<<Caliper[3].angle<<"\n";
fout<<"Caliper 4: "<<Caliper[4].P.id<<" "<<Caliper[4].angle<<"\n";
*/
double dmin=180;
int cmin;
for(int i=1; i<=4; ++i)
{
double delta=abs(angle(Caliper[i].P, H[(Caliper[i].P.id<k)?Caliper[i].P.id+1:1])-Caliper[i].angle);
if(delta<dmin){
dmin=delta;
cmin=i;
}
}
//fout<<"rotation by "<<dmin<<"\n";
for(int i=1; i<=4; ++i)
Caliper[i].angle+=dmin;
Caliper[cmin].P=H[(Caliper[cmin].P.id<k)?Caliper[cmin].P.id+1:1];
double dist12 = sqrt(pow(Caliper[1].P.x-Caliper[2].P.x,2) + pow(Caliper[1].P.y-Caliper[2].P.y,2));
double dist34 = sqrt(pow(Caliper[3].P.x-Caliper[4].P.x,2) + pow(Caliper[3].P.y-Caliper[4].P.y,2));
double area=dist12*sin(abs(angle(Caliper[1].P, Caliper[2].P)-Caliper[1].angle))*dist34*sin(abs(angle(Caliper[3].P, Caliper[4].P)-Caliper[3].angle));
//fout<<"current area :"<<area<<"\n";
if(area<amin)
amin=area;
trotation+=dmin;
}
fout<<amin;
}