Cod sursa(job #1091627)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 25 ianuarie 2014 21:09:24
Problema Aria Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<algorithm>
#include<deque>

using namespace std;

ifstream f("aria.in");
ofstream g("aria.out");

struct QQ{
    double x;
    double y;
    double p;
};

bool cmp1(QQ i, QQ j){
    if(i.x==j.x)
        return i.y<j.y;
    else
        return i.x<j.x;
}

bool cmp2(QQ i, QQ j){
    return i.p<j.p;
}

QQ a[100005];
deque<int> b;


int main(){
    int n,i,j,x1,y1,xx1,xx2,k,q,w;
    double m;

    f>>n;

    for(i=1; i<=n; ++i){
        f>>a[i].x>>a[i].y;
    }

    sort(a+1,a+n+1, cmp1);

    xx1=a[n].x; xx2=a[n].y;

    x1=a[1].x; y1=a[1].y;
    for(i=2; i<=n; ++i){
        a[i].p=(a[i].y-y1)/(a[i].x-x1);
    }

    sort(a+2, a+n+1,cmp2);

    a[n+1]=a[1];

    b.push_back(1);
    b.push_back(2);
    b.push_back(3);

    if(n>3){
    for(i=1; i<n-1; ++i){
        k=b[b.size()-3];
        q=b[b.size()-2];
        w=b.back();
        m=(a[q].y-a[k].y)*(a[w].x - a[q].x) - (a[w].y - a[q].y)*(a[q].x - a[k].x);

        if(m>0){
            b[b.size()-2]=b.back();
            b.pop_back();
            b.push_back(b.back()+1);
        }
        else{
            b.push_back(b.back()+1);
        }

    }

    }

    double space=0;

    for(i=1; a[i].x!=xx1 && a[i].y!=xx2;  ++i){
        space-=(a[b[i]].x-a[b[i-1]].x)/2*(a[b[i]].y + a[b[i-1]].y);
        j=i;
    }

    for(i=j; i<b.size(); ++i){
        space+=(a[b[i]].x-a[b[i+1]].x)/2*(a[b[i+1]].y + a[b[i+1]].y);
    }

    g<<space;

return 0;
}