Cod sursa(job #2101731)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 7 ianuarie 2018 21:33:07
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <cstdio>
#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 * b.x * c.y + 1LL * c.x *a.y - 1LL * a.x * c.y - 1LL * b.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[100005];
punct V[100005];
int N,len;
int nxt[100005];
double rez = 1e18;
double u = atan2(0,1);
int main(){
    fscanf(f,"%d",&N);
    for(int i = 1;i <= N;i++){
        fscanf(f,"%d %d",&V[i].x,&V[i].y);
    }
    sort(V + 1,V + 1 + N);
    for(int i = 1;i <= N;i++){
        while(len > 1 && det(hull[len - 1],hull[len],V[i]) <= 0){
            len--;
        }
        hull[++len] = V[i];
    }
    reverse(V + 1,V + 1 + N);
    for(int i = 1;i <= N;i++){
        while(len > 1 && det(hull[len - 1],hull[len],V[i]) <= 0){
            len--;
        }
        hull[++len] = V[i];
    }
    len--;
    if(len < 3){
        fprintf(g,"%.2f",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 = further % len + 1;
        }
        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 = (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;
}