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.