Cod sursa(job #2101894)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 8 ianuarie 2018 10:53:08
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <cstdio>
#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 a < b;
}
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]) <= 0){
            len--;
        }
        hull[++len] = V[i];
    }
    len--;
}
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,"%.2f",(double)0);
        return 0;
    }
    for(int i = 1;i < len;i++){
        nxt[i] = i + 1;
    }
    nxt[len] = 1;
    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(det(P1,P2,hull[further]) <= det(P1,P2,hull[nxt[further]])){
            further = nxt[further];
        }
        if(i == 1){
            leftmost = further;
        }
        while(dotProduct({hull[leftmost].x - hull[nxt[leftmost]].x,hull[leftmost].y - hull[nxt[leftmost]].y},{P2.x - P1.x,P2.y - P1.y}) >= 0){
            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}) >= 0){
            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;
        double H = abs(a * hull[further].x + b * hull[further].y + c) / sqrt(a * a + b * b);
        double W = rotAndGetX({hull[rightmost].x - hull[leftmost].x,hull[rightmost].y - hull[leftmost].y},atan2(P2.y - P1.y,P2.x - P1.x) - u);
        rez = min(rez,abs(H * W));
    }
    fprintf(g,"%.2f",rez);
    fclose(f);
    fclose(g);
    return 0;
}