Cod sursa(job #913878)

Utilizator Sm3USmeu Rares Sm3U Data 13 martie 2013 20:25:58
Problema Aria Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>

#define nMax 100010
#define oo 1 << 30

#define abs(a) ((a<0)?-a:a)

using namespace std;

struct puncte{
    double x;
    double y;
}a[nMax * 2];

int n;
double min = oo;
int pMin;
double max = -oo;
int pMax;
double yMin = oo;

void citire(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i){
        scanf("%lf %lf", &a[i].x, &a[i].y);
        if(yMin > a[i].y){
            yMin = a[i].y;
        }
        if(max <= a[i].x){
            if(max == a[i].x){
                if(a[pMax].y > a[i].y){
                    pMax = i;
                }
            }else{
                max = a[i].x;
                pMax = i;
            }
        }
        if(min >= a[i].x){
            if(min == a[i].x){
                if(a[pMin].y > a[i].y){
                    pMin = i;
                }
            }else{
                min = a[i].x;
                pMin = i;
            }
        }
    }
}


double arie(puncte a1, puncte a2){
    /**
        a1.x  |  a1.y  |   1
        a2.x  |  a2.y  |   1
        0     |  yMin  |   1
    */
    double determinant = 0;
    determinant = a1.x * a2.y + a2.x * yMin - yMin * a1.x - a1.y * a2.x;
    return abs(determinant) / 2;

}

void rez(){
    yMin --;
    int i = 1;
    for(int i = 0; i < n; ++ i){
        a[n + i] = a[i];
    }
    if(pMax <= pMin){
        i = pMax + 1;
        pMax += n;
    }
    double s = 0;
    for(i; i <= pMin; ++ i){
        s += arie (a[i - 1], a[i]);
    }
    for(i = pMin + 1; i <= pMax; ++ i){
        s -= arie (a[i - 1], a[i]);
    }
    for(int i = pMax + 1; i <= n; ++ i){
        s += arie(a[i - 1], a[i]);
    }
    printf("%lf", s);
}

int main()
{
    freopen("aria.in", "r", stdin);
    freopen("aria.out", "w", stdout);

    citire();
    rez();

    return 0;
}