Cod sursa(job #1664036)

Utilizator sorynsooSorin Soo sorynsoo Data 26 martie 2016 11:49:12
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
#define MAXN 100005

struct pc
{
    long long x, y, id;
}crt, st[MAXN];

vector<pc> v, q;
int sum[MAXN], n, m, nrst;

double determinant(pc A, pc B, pc C)
{
     return (A.x - B.x)*(B.y - C.y) - (B.x - C.x)*(A.y - B.y);
}

bool cmp(pc A, pc B)
{
    return determinant(v[0], A, B) > 0;
}

void update(pc ST[], int &NRST, pc pc_c)
{
    while( NRST >=2 && determinant( ST[ NRST-1 ] , ST[ NRST ] , pc_c ) < 0 )
        NRST --;

    st[ ++NRST ] = pc_c;
}

double arie_calc(pc ST[], int NRST)
{
    double a = 0;
    for(int i=2; i<NRST; i++)
        a += ( determinant(ST[1], ST[i], ST[i+1]) / (double)2 );
    return a;
}
int main()
{
    int i, j;
    freopen("geometrie.in", "r", stdin);
    freopen("geometrie.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d", &crt.x, &crt.y); crt.id = 1;
        v.push_back( crt );
    }

    for(i=1; i<=m; i++)
    {
        scanf("%d %d", &crt.x, &crt.y); crt.id = 2;
        q.push_back( crt );
        v.push_back( crt );
    }

    sort(v.begin(), v.end(), cmp);

    for(i=0;  i < q.size(); i++)
    {
        for(j=0; j < v.size(); j++)
            if(( v[j].x < q[i].x  &&  v[j].id == 1 ) || ( q[i].x == v[j].x && q[i].y == v[j].y ) )
                update(st, nrst, v[j]);

         printf("%.1llf \n", arie_calc(st, nrst));
         nrst=0;

    }
}