## 361 Again!!!

Moderator: Board moderators

Hello,
I have written the code that implements finding of convex hulls (AM method) and then determines whether the point is inside it or outside it. Could someone provide some more sample input, because for the one provided in the task and in this thread and some examples generated by hand the results are ok (and I've tripple checked the formatting of the output).

Regards,
Milosz
mhulboj
New poster

Posts: 4
Joined: Fri Jun 10, 2005 2:02 pm

Check the samples...

Input:
Code: Select all
`4 4 100 020 00 2020 2010 -1010 3015 -1015 301 10 020 1912 1210 2210 3110 20-1 -115 2115 200 0 0`

Output:
Code: Select all
`Data set 1:     Citizen at (1,1) is safe.     Citizen at (0,0) is safe.     Citizen at (20,19) is safe.     Citizen at (12,12) is safe.     Citizen at (10,22) is robbed.     Citizen at (10,31) is neither.     Citizen at (10,20) is safe.     Citizen at (-1,-1) is neither.     Citizen at (15,21) is robbed.     Citizen at (15,20) is safe.`

Hope these help.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Thanks,
This output was OK, but I've tried few more manually generated and found an awfully stupid copy/paste bug in my code. After fixing got AC.
And for those seeking solution be sure to handle these cases properly:
Code: Select all
`2 0 10 00 00 03 0 10 00 00 00 03 0 1-2 02 00 01 03 0 10 -20 20 10 -1`
mhulboj
New poster

Posts: 4
Joined: Fri Jun 10, 2005 2:02 pm

Keep getting WA...
What sould be the output for mhulboj's testcase?

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

For his input (added 3 0's at the end), my freshly AC program outputs:
Code: Select all
`Data set 1:     Citizen at (0,0) is neither.Data set 2:     Citizen at (0,0) is safe.Data set 3:     Citizen at (1,0) is safe.Data set 4:     Citizen at (0,-1) is safe.`
Darko
Guru

Posts: 572
Joined: Fri Nov 11, 2005 9:34 am

Thanks, Darko. It seems that I'm handling them well.

Is there any other tricky test case ?

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

I don't have any special cases - I just find convex hulls if there are more than 2 points, if not, I ignore them (note that "convex hull" might contain less than 3 points). Maybe it is your point-in-polygon? I first check if the "other" point coincides with a vertex of the polygon, then, if not, I check if it is on an edge and then if it is inside. I guess once you have a tested code to do it, it should be straightforward.
Darko
Guru

Posts: 572
Joined: Fri Nov 11, 2005 9:34 am

### Re: 361 - Cops and Robbers

Don't know whats going wrong, getting WA in this problem. I have tested inputs already posted on these forums, but those could not help me to find the bug. Here is my code:
Code: Select all
`#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;const int MAXN = 256;struct point { int x, y; };struct region { bool ok; int np; point P[MAXN]; };region K[2];point P[MAXN], C[MAXN], P0;inline int triArea2(const point &a, const point &b, const point &c) {   return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));}inline int sqDist(const point &a, const point &b) {   return ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));}inline bool comp(const point &a, const point &b) {   int d = triArea2(P0, a, b);   if(d < 0) return false;   if(!d && sqDist(P0, a) > sqDist(P0, b)) return false;   return true;}inline bool normal(const point &a, const point &b) {   return ((a.x==b.x) ? a.y < b.y : a.x < b.x);}inline bool issame(const point &a, const point &b) {   return (a.x == b.x && a.y == b.y);}inline void makeUnique(int &np) {   sort(&P[0], &P[np], normal);   np = unique(&P[0], &P[np], issame) - P;}void convexHull(int &np, int &nc) {   int i, j, pos = 0;   for(i = 1; i < np; i++)      if(P[i].y<P[pos].y || (P[i].y==P[pos].y && P[i].x<P[pos].x))         pos = i;   swap(P[0], P[pos]);   P0 = P[0];   sort(&P[1], &P[np], comp);   for(i = 0; i < 3; i++) C[i] = P[i];   for(i = j = 3; i < np; i++) {      while(triArea2(C[j-2], C[j-1], P[i]) < 0) j--;      C[j++] = P[i];   }   nc = j;}bool inside(point *p, int n, point &m) {   if(n == 1) return p[0].x == m.x && p[0].y == m.y;   if(n == 2) return (sqDist(p[0], m) + sqDist(m, p[1]) <= sqDist(p[0], p[1]));   int lt = n - 1, rt = 1, mid, dir, temp;   while(lt - rt > 1) {      mid = (lt + rt) >> 1;      dir = triArea2(p[0], p[mid], m);      if(dir < 0) lt = mid;      else if(dir > 0) rt = mid;      else return (sqDist(p[0], m) + sqDist(m, p[mid]) <= sqDist(p[0], p[mid]));   }   temp = abs(triArea2(p[0], p[rt], m)) + abs(triArea2(p[rt], p[lt], m)) + abs(triArea2(p[lt], p[0], m));   return (temp == abs(triArea2(p[0], p[rt], p[lt])));}int main() {   int n[2], c[2], i, kd, cit, cs = 1;   point m;   while(scanf("%d%d%d", &n[0], &n[1], &cit)==3 && (n[0] + n[1] + cit)) {      for(kd = 0; kd < 2; kd++) {         for(i = 0; i < n[kd]; i++) scanf("%d%d", &P[i].x, &P[i].y);         if(n[kd] < 3) { K[kd].ok = 0; continue; }         K[kd].ok = 1;         makeUnique(n[kd]);         if(n[kd] < 3) {            K[kd].np = n[kd];            for(i = 0; i < n[kd]; i++) K[kd].P[i] = P[i];            continue;         }         convexHull(n[kd], c[kd]);         K[kd].np = c[kd];         for(i = 0; i < c[kd]; i++) K[kd].P[i] = C[i];      }      printf("Data set %d:\n", cs++);      for(i = 0; i < cit; i++) {         scanf("%d%d", &m.x, &m.y);         if(K[0].ok && inside(K[0].P, K[0].np, m)) printf("     Citizen at (%d,%d) is safe.\n", m.x, m.y);         else if(K[1].ok && inside(K[1].P, K[1].np, m)) printf("     Citizen at (%d,%d) is robbed.\n", m.x, m.y);         else printf("     Citizen at (%d,%d) is neither.\n", m.x, m.y);      }      printf("\n");   }   return 0;}`

If I have < 3 cops or robbers, I will ignore them. Then I find their convex hulls, which might not be strictly convex. Then I determine where the citizen falls... I think this is correct.

You should not always say what you know, but you should always know what you say.
zobayer
Experienced poster

Posts: 110
Joined: Tue May 06, 2008 2:18 pm

### Re: 361 Again!!!

Can I have the .exe of your AC code for 361.I am getting WA in this problem also.
Or,please tell me what is the critical test case for which I should concerned.

Or,please have a look on my code.

Code: Select all
`#include<stdio.h>#include<math.h>#include<string.h>#include<iostream>#include<queue>#include<vector>#include<map>using namespace std;#define EPS 1e-9struct PT{    int x,y;}c[210],r[210],p[210]; double dist(PT &a,PT &b){     return (sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));     }double area(int x1,int y1,int x2,int y2,int x3,int y3){   double a;    a=0.5*((x1*y2+x2*y3+x3*y1)-(y1*x2+y2*x3+y3*x1));     return fabs(a);}int ifinside(PT k,PT ul,PT lr,PT tr){/*double a[5];a[0]=dist(ul,lr);a[1]=dist(lr,tr);a[2]=dist(ul,tr);sort(a,a+3);if((a[0]+a[1])>a[2]){*/      double a1,a2,a3,a4;         a1=area(k.x,k.y,ul.x,ul.y,lr.x,lr.y);         a2=area(k.x,k.y,ul.x,ul.y,tr.x,tr.y);         a3=area(k.x,k.y,tr.x,tr.y,lr.x,lr.y);         a4=area(ul.x,ul.y,lr.x,lr.y,tr.x,tr.y);     if((a1+a2+a3-a4)<=EPS)         return 1;      else      return 0;/*}else      return 0;*/}int main(){int cr,rb,ct,i,j,k,l,cops,robbed,set;//freopen("361.txt","r",stdin);set=0;while(scanf("%d %d %d",&cr,&rb,&ct)==3){if(cr==0 && rb==0 &&ct==0) break;for(i=0;i<cr;i++){scanf("%d %d",&c[i].x,&c[i].y);}for(i=0;i<rb;i++){scanf("%d %d",&r[i].x,&r[i].y);}printf("Data set %d:\n",++set);for(i=0;i<ct;i++){scanf("%d %d",&p[i].x,&p[i].y);cops=0;for(j=0;j<cr-2;j++){  for(k=j+1;k<cr-1;k++){       { if(ifinside(p[i],c[j],c[k],c[k+1])==1)                {cops=1;break;}      }    if(cops==1)  break;      }if(cops==1)  break;}robbed=0;for(j=0;j<rb-2;j++){  for(k=j+1;k<rb-1;k++){     {    if(ifinside(p[i],r[j],r[k],r[k+1])==1)                {robbed=1;break;}      }    if(robbed==1)  break;      }if(robbed==1)  break;}if(cops==1)printf("     Citizen at (%d,%d) is safe.\n",p[i].x,p[i].y);else if(robbed==1)printf("     Citizen at (%d,%d) is robbed.\n",p[i].x,p[i].y);elseprintf("     Citizen at (%d,%d) is neither.\n",p[i].x,p[i].y);}printf("\n");}return 0;}`

my mail id is
Code: Select all
`usuttra@yahoo.com `

ujjal.ruet
New poster

Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm

### Re: 361 Again!!!

You can find EXEs of most of the UVa problems in this site - http://uvatoolkit.com/problemssolve.php

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

Previous