Pagini recente » Cod sursa (job #2930827) | Cod sursa (job #2980599) | Cod sursa (job #2663518) | Cod sursa (job #2046441) | Cod sursa (job #1664036)
#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;
}
}