Pagini recente » Cod sursa (job #2721406) | Cod sursa (job #2749509) | Cod sursa (job #2923658) | Cod sursa (job #1980282) | Cod sursa (job #1395422)
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
int n;
double sum=0;
struct str
{
double x;
double y;
double n1;
double n2;
}a[120001],b[120001],q;
double comp(str a,str b)
{
return (a.n1*b.n2) < (b.n1*a.n2);
}
double calcarie(double x1,double y1,double x2,double y2,double x3,double y3)
{
double arie=double((double)x1*(y2-y3)+(double)x2*(y3-y1)+(double)x3*(y1-y2));
arie=(double)arie/2;
return arie;
}
int stack[120001];
int pint,nr,m;
int main()
{
ifstream f("geometrie.in");
ofstream g("geometrie.out");
f>>nr>>m;
for (int i=1;i<=nr ;i++ )
f>>b[i].x>>b[i].y;
for (int qiu=1;qiu<=m ;qiu++ )
{
f>>q.x>>q.y;
int n=0;
for (int i=1;i<=nr ;i++ )
if(b[i].x<q.x)
{
n++;
a[n]=b[i];
}
n++; a[n]=q;
double minx=1000000001,miny=1000000001;
int indice;
for(int i=1;i<=n;i++)
{
if(minx>a[i].x)
{
minx=a[i].x;
miny=a[i].y;
indice=i;
}
else if(minx==a[i].x&&miny>a[i].y)
{
miny=a[i].y;
indice=i;
}
}
for(int i=1;i<indice;i++)
{
a[i].n1=a[i].y-a[indice].y;
a[i].n2=a[i].x-a[indice].x;
}
for(int i=indice+1;i<=n;i++)
{
a[i].n1=a[i].y-a[indice].y;
a[i].n2=a[i].x-a[indice].x;
}
swap(a[1],a[indice]);
sort(a+2,a+n+1,comp);
stack[1]=1;
stack[2]=2;
pint=3;
for(int i=3;i<=n;i++)
{
while(calcarie(a[stack[pint-2]].x,a[stack[pint-2]].y,a[stack[pint-1]].x,a[stack[pint-1]].y,a[i].x,a[i].y)<0) pint--;
stack[pint]=i;
pint++;
}
//pint-1=n;
a[stack[0]]=a[stack[pint-1]];
int i,j,k;
sum=0;
for ( i=1, j=2, k=0; i<pint-1; i++, j++, k++) //a[stack[i]].x //a[stack[i]].y
sum=sum+a[stack[i]].x*(a[stack[j]].y-a[stack[k]].y); // V[n].x * (V[1].y - V[n-1].y);
sum=sum+a[stack[pint-1]].x*(a[stack[1]].y-a[stack[pint-2]].y);
g<<fixed<<setprecision(1)<<sum/2<<'\n';
}
}