https://www.spoj.pl/problems/AMR10A/
Logic :
Cannot find the area on the fly for all Q
- Precompute the area of all polygons with a segment joining
0 and x as end points.
- We can do this by using area of [0,x-1] and area of triangle
[0,x-1,x]
I have implemented this but i am not able to find my error and i am
getting wrong answer continuously.
Someone help.
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int n,q;
int i,j,k;
scanf("%d%d",&n,&q);
int x[50009],y[50009];
double pro[50009];
for(i=0;i<n;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
x[n]=x[0];
y[n]=y[0];
double p,p2;
double sum=0.0,sum2=0.0,sum3=0.0;
double area[50009];
double a1,a2,a3;
double ar;
pro[0]=(x[0]*y[1])-(x[1]*y[0]);
pro[1]=(x[1]*y[2])-(x[2]*y[1]);
sum+=pro[0]+pro[1];
area[0]=area[1]=0.0;
for(i=2;i<n;i++)
{
a1=(x[0]*y[i-1])-(x[i-1]*y[0]);
a2=(x[i-1]*y[i])-(x[i]*y[i-1]);
a3=(x[i]*y[0])-(x[0]*y[i]);
ar=(a1+a2+a3)/2;
ar=fabs(ar);
area[i]=ar+area[i-1];
}
sum=area[n-1];
int a,b;
for(i=0;i<q;i++)
{
sum2=0.0;
scanf("%d%d",&a,&b);
if(a!=0)
{
a1=(x[0]*y[a])-(x[a]*y[0]);
a2=(x[a]*y[b])-(x[b]*y[a]);
a3=(x[b]*y[0])-(x[0]*y[b]);
ar=(a1+a2+a3)/2;
ar=fabs(ar);
ar+=area[a];
sum2=area[b]-ar;
sum2=fabs(sum2);
}
else{
sum2=area[b];
}
sum3=sum-sum2;
if(sum2<sum3)
printf("%.1lf\n",sum2);
else
printf("%.1lf\n",sum3);
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
