Pagini recente » Cod sursa (job #2682496) | Cod sursa (job #1951877) | Cod sursa (job #3287872) | soldiers | Cod sursa (job #3284470)
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
using namespace std;
#define NMAX 100001
#define INF 1000001
int n;
struct point{
double x, y;
friend bool operator<(point p1, point p2){
if (p1.x==p2.x)return p1.y<p2.y;
return p1.x<p2.x;
}
point operator+=(point p1){
this->x+=p1.x;
this->y+=p1.y;
return *this;
}
point operator/=(double ii){
this->x/=ii;
this->y/=ii;
return *this;
}
} a[NMAX], w[NMAX];
vector<int> st;
bool used[NMAX];
double rem_stack(point p1, point p2, point p3){
return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y));
}
void conv(){
st.push_back(1);
st.push_back(2);
used[2]=true;
for (int i=3; i<=n; ++i){
if (used[i])continue;
while (st.size()>=2 && .0>=rem_stack(a[st[st.size()-2]], a[st[st.size()-1]], a[i])){
used[st.back()]=false;
st.pop_back();
}
used[i]=true;
st.push_back(i);
}
for (int i=n; i>0; --i){
if (used[i])continue;
while (st.size()>=2 && .0>=rem_stack(a[st[st.size()-2]], a[st[st.size()-1]], a[i])){
used[st.back()]=false;
st.pop_back();
}
used[i]=true;
st.push_back(i);
}
//st.pop_back();
}
int main(){
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out", "w", stdout);
cin>>n;
for (int i=1; i<=n; ++i){
cin>>a[i].x>>a[i].y;
}
sort(a+1, a+n+1);
//for (int i=1; i<=n; ++i)cout<<i<<": "<<a[i].x<<" "<<a[i].y<<endl;
conv();
//cout<<endl; for (auto it:st)cout<<it<<": "<<a[it].x<<" "<<a[it].y<<endl;
/// please explain
double ans = INF;
for (int i=0; i<st.size(); ++i){
int next_i=(i+1)%st.size();
double unghi=atan2(a[st[next_i]].y-a[st[i]].y, a[st[next_i]].x-a[st[i]].x);
unghi=-unghi;
double xmax=-INF, xmin=INF;
double ymax=-INF, ymin=INF;
for (int j=0; j<st.size(); ++j) {
w[j].x=a[st[j]].x*cos(unghi)-a[st[j]].y*sin(unghi);
w[j].y=a[st[j]].x*sin(unghi)+a[st[j]].y*cos(unghi);
xmax = max(xmax, w[j].x);
xmin = min(xmin, w[j].x);
ymax = max(ymax, w[j].y);
ymin = min(ymin, w[j].y);
}
double arie=(xmax-xmin)*(ymax-ymin);
ans=min(ans, arie);
}
cout<<setprecision(2)<<fixed<<ans;
/* sol pt calculat aria strict a infasuratoarei convexe
point mid={.x=0, .y=0};
for (auto it:st){
//cout<<a[it].x<<" "<<a[it].y<<endl;
mid+=a[it];
}
mid/=double(st.size());
//cout<<mid.x<<" "<<mid.y;
double area=.0, calc_area=[](point p1, point p2, point p3){
double c=p1.x*p2.y+p2.x*p3.y+p3.x*p1.y
-p3.x*p2.y-p1.x*p3.y-p2.x*p1.y;
return .5*(c<.0 ? -c : c);
};
for (int i=0; i<st.size(); ++i){
int j=(i+1)%st.size();
area+=calc_area(a[i], a[j], mid);
}
cout<<setprecision(2)<<fixed<<area;
*/
return 0;
}