Mai intai trebuie sa te autentifici.
Cod sursa(job #1210623)
Utilizator | Data | 20 iulie 2014 17:21:35 | |
---|---|---|---|
Problema | Rubarba | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.1 kb |
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef long long int lld;
const int NMAX = 100000+5;
const int INF = (1<<30);
const double PI = acos(-1.0);
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
int N,M;
PII P[NMAX];
PII H[NMAX];
double sol;
inline lld crossProd(PII A,PII B,PII C)
{
return (B.first-A.first)*(C.second-A.second)-(C.first-A.first)*(B.second-A.second);
}
inline bool cmp(PII A,PII B)
{
return crossProd(P[1],A,B)>0;
}
inline PDD rotate(PII A,double alfa)
{
alfa=-alfa;
double x,y;
x=A.first*cos(alfa)-A.second*sin(alfa);
y=A.first*sin(alfa)+A.second*cos(alfa);
return make_pair(x,y);
}
void convexHull();
int main()
{
int i,j;
double x,y,z,alfa;
double xmin,ymin,xmax,ymax;
PDD Q;
fin>>N;
for(i=1; i<=N; i++)
fin>>P[i].first>>P[i].second;
convexHull();
if(M<=2)
{
fout<<fixed<<setprecision(2)<<sol;
return 0;
}
H[M+1]=H[1];
sol=INF;
for(i=1; i<=M; i++)
{
x=H[i+1].first-H[i].first;
y=H[i+1].second-H[i].second;
z=sqrt(x*x+y*y);
alfa=acos(x/z);
if(y<0) alfa=-alfa;
//fout<<alfa*180.0/PI<<" ";
ymin=xmin=INF;
ymax=xmax=-INF;
for(j=1; j<=M; j++)
{
Q=rotate(H[j],alfa);
if(Q.first<xmin) xmin=Q.first;
if(Q.first>xmax) xmax=Q.first;
if(Q.second<ymin) ymin=Q.second;
if(Q.second>ymax) ymax=Q.second;
}
sol=min(sol,(xmax-xmin)*(ymax-ymin));
//fout<<(xmax-xmin)*(ymax-ymin)<<'\n';
}
fout<<fixed<<setprecision(2)<<sol;
return 0;
}
void convexHull()
{
int i;
sort(P+1,P+N+1);
sort(P+2,P+N+1,cmp);
H[++M]=P[1];
H[++M]=P[2];
for(i=3; i<=N; i++)
{
while(M>=2 && crossProd(H[M-1],H[M],P[i])<0) M--;
H[++M]=P[i];
}
}