C++】
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <utility>
#include <iostream>
#include <cmath>
using namespace std;
const double oo = 1e20;
typedef pair<double , double> Point;
Point Origin;
stack<Point> H;
vector<Point> S , Q;
int N;
double Ans;
Point operator - (const Point& a , const Point& b){
Point c(a.first-b.first , a.second-b.second);
return c;
}
bool counterclockwise(const Point& p , const Point& q){
Point a = p-Origin , b = q-Origin;
if (a.first*b.second-a.second*b.first > 0) return true;
return false;
}
inline void swap(Point &u , Point &v){
Point tmp = u;
u = v ; v = tmp;
}
void init(){
int i;
double p , q;
Point tmp;
scanf("%d" , &N);
for (i = 0 ; i < N ; i++) {
scanf("%lf %lf" , &p , &q);
tmp = make_pair(p , q);
S.push_back(tmp);
}
}
void GetCH(){
int i;
for (i = 1 ; i < N ; i++)
if (S[0] > S[i]) swap(S[0] , S[i]);
Origin = S[0];
sort(S.begin()+1 , S.begin()+N , counterclockwise);
Point u , v;
H.push(S[0]);
Origin = make_pair(0 , 0);
for (i = 1 ; i < N ; i++) {
while (H.size() >= 2) {
u = H.top(); H.pop(); v = H.top();
if (counterclockwise(u-v , S[i]-u)) {
H.push(u);
break;
}
}
H.push(S[i]);
}
for ( ; H.size() > 0 ; ) {
Q.push_back(H.top());
H.pop();
}
for (i = 0 ; Q.size()-1-i > i ; i++)
swap(Q[i] , Q[Q.size()-1-i]);
}
inline double dot(Point a , Point b){
return a.first*b.first+a.second*b.second;
}
inline int nextp(const int& v){
return (v+1)%Q.size();
}
inline Point GetNormal(Point v){
Point r(-1*v.second , v.first);
return r;
}
inline double dist(Point v){
return sqrt(v.first*v.first+v.second*v.second);
}
void update(int& cur , Point normal , Point orig){
int ncur = nextp(cur);
while (dot(Q[ncur]-orig , normal) > dot(Q[cur]-orig , normal)) {
cur = ncur;
ncur = nextp(cur);
}
}
double Calc(int r , int l , int u , int cur , int nex){
double p , q;
p = dot(Q[r]-Q[cur] , Q[nex]-Q[cur])/dist(Q[nex]-Q[cur])
+ dot(Q[l]-Q[nex] , Q[cur]-Q[nex])/dist(Q[nex]-Q[cur])
- dist(Q[nex]-Q[cur]);
q = dot(Q[u]-Q[cur] , GetNormal(Q[nex]-Q[cur]))/dist(GetNormal(Q[nex]-Q[cur]));
return p*q;
}
void GetAns(){
int i , j , righthand , lefthand , upside;
Ans = oo;
initialize righthand point
righthand = 1;
initialize lefthand point
for (i = 2 ; i < Q.size() ; i++)
if (dot(Q[i]-Q[1] , Q[0]-Q[1]) > 0) break;
if (i >= Q.size()) lefthand = 0;
else lefthand = i;
initialize upside point
Point normal = GetNormal(Q[1]-Q[0]);
upside = 1;
Scan
for (i = 0 ; i < Q.size() ; i++) {
j = nextp(i);
update(righthand , Q[j]-Q[i] , Q[i]);
update(lefthand , Q[i]-Q[j] , Q[j]);
update(upside , GetNormal(Q[j]-Q[i]) , Q[i]);
Ans <?= Calc(righthand , lefthand , upside , i , j);
}
}
void outp(){
printf("%.2lf/n" , Ans);
}
int main(){
freopen("ch.out" , "w" , stdout);
freopen("ch.in" , "r" , stdin);
init();
GetCH();
GetAns();
outp();
fclose(stdin);
fclose(stdout);
return 0;
}
