Cod sursa(job #2101966)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 8 ianuarie 2018 12:03:23
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.82 kb
#include <cstdio>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
FILE *f = fopen("rubarba.in","r");
FILE *g = fopen("rubarba.out","w");
struct punct{
    int x,y;
    bool operator < (const punct &other)const{
        if(x != other.x){
            return x < other.x;
        }
        return y < other.y;
    }
};
long long det(punct a,punct b,punct c){
    return 1LL * a.x * b.y - 1LL * a.x * c.y + 1LL * b.x * c.y - 1LL * b.x * a.y + 1LL * c.x *a.y - 1LL * c.x * b.y;
}
long long dotProduct(punct a,punct b){
    return 1LL * a.x * b.x + 1LL * a.y * b.y;
}
double rotAndGetX(punct P,double teta){
    return ((double)P.x) * cos(teta) + ((double)P.y) * sin(teta);
};
punct hull[200005];
punct lower[200005];
punct upper[200005];
punct V[100005];
int N,len,len2;
int nxt[200005];
double rez = 1e18;
double u = atan2(0,1);
void hullStack(){
    sort(V + 1,V + 1 + N);
    for(int i = 1;i <= N;i++){
        while(len > 1 && det(lower[len - 1],lower[len],V[i]) <= 0){
            len--;
        }
        lower[++len] = V[i];
    }
    reverse(V + 1,V + 1 + N);
    for(int i = 1;i <= N;i++){
        while(len2 > 1 && det(upper[len2 - 1],upper[len2],V[i]) <= 0){
            len2--;
        }
        upper[++len2] = V[i];
    }
    for(int i = 1;i <= len;i++){
        hull[i] = lower[i];
    }
    for(int i = 2;i < len2;i++){
        hull[++len] = upper[i];
    }
}
bool cmp(punct a,punct b){
    if(det(V[1],a,b)){
        return det(V[1],a,b) > 0;
    }
    return 1LL * (a.x - V[1].x) * (a.x - V[1].x) + 1LL * (a.y - V[1].y) * (a.y - V[1].y) <= 1LL * (b.x - V[1].x) * (b.x - V[1].x) + 1LL * (b.y - V[1].y) * (b.y - V[1].y);
}
void hullGraham(){
    for(int i = 2;i <= N;i++){
        if(V[i] < V[1]){
            swap(V[i],V[1]);
        }
    }
    sort(V + 2,V + 1 + N,cmp);
//    int ind = N;
//    while(ind >= 2 && det(V[1],V[ind],V[ind - 1]) == 0){
//        ind--;
//    }
//    if(ind == 1){
//        return ;
//    }
//    reverse(V + ind,V + 1 + N);
    V[N + 1] = V[1];
    for(int i = 1;i <= N + 1;i++){
        while(len > 1 && det(hull[len - 1],hull[len],V[i]) < - 1e-14){
            len--;
        }
        hull[++len] = V[i];
    }
    len--;
}
double Dist(punct P,long long a,long long b,long long c){
    return abs(a * P.x + b * P.y + c) / sqrt(a * a + b * b);
}
int main(){
    fscanf(f,"%d",&N);
    for(int i = 1;i <= N;i++){
        fscanf(f,"%d %d",&V[i].x,&V[i].y);
    }
//    hullStack();
    hullGraham();
    if(len < 3){
        fprintf(g,"%.4f",(double)0);
        return 0;
    }
    for(int i = 1;i < len;i++){
        nxt[i] = i + 1;
    }
    nxt[len] = 1;
    for(int i = 1;i <= len;i++){
        assert(hull[i].x != hull[nxt[i]].x || hull[i].y != hull[nxt[i]].y);
    }
    int further = 2;
    int leftmost = 1;
    int rightmost = 2;
    for(int i = 1;i <= len;i++){
        punct P1 = hull[i],P2 = hull[nxt[i]];
        while(1e-14 <= abs(det(P1,P2,hull[nxt[further]])) - abs(det(P1,P2,hull[further]))){
            further = nxt[further];
        }
        if(i == 1){
            leftmost = further;
        }
        while(dotProduct({hull[nxt[leftmost]].x - hull[leftmost].x,hull[nxt[leftmost]].y - hull[leftmost].y},{P2.x - P1.x,P2.y - P1.y}) <= -1e-14){
            leftmost = nxt[leftmost];
        }
        while(dotProduct({hull[nxt[rightmost]].x - hull[rightmost].x,hull[nxt[rightmost]].y - hull[rightmost].y},{P2.x - P1.x,P2.y - P1.y}) >= 1e-14){
            rightmost = nxt[rightmost];
        }
        long long a,b,c;
        a = P2.y - P1.y;
        b = P1.x - P2.x;
        c = 1LL * P2.x * P1.y - P1.x * P2.y;
        assert(a || b);
        double H = Dist(hull[further],a,b,c);
        double W = Dist(hull[rightmost],-b,a,b * hull[leftmost].x - a * hull[leftmost].y);
        assert(H > 0 && W > 0);
        rez = min(rez,H * W);
    }
    fprintf(g,"%.4f",rez);
    fclose(f);
    fclose(g);
    return 0;
}