361 Again!!!

[mhulboj]

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

[Jan]

Check the samples...

Input:

Code: Select all

4 4 10
0 0
20 0
0 20
20 20
10 -10
10 30
15 -10
15 30
1 1
0 0
20 19
12 12
10 22
10 31
10 20
-1 -1
15 21
15 20
0 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.

[mhulboj]

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 1
0 0
0 0
0 0
3 0 1
0 0
0 0
0 0
0 0
3 0 1
-2 0
2 0
0 0
1 0
3 0 1
0 -2
0 2
0 1
0 -1


[rio]

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

[Darko]

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.



[rio]

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

Is there any other tricky test case ?

Thanks in advance.

[Darko]

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.

[zobayer]

Problem Link: http://uva.onlinejudge.org/external/3/361.html
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.

Please help me, thanks in advance

[ujjal.ruet]

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-9

struct 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);
else
printf("     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

please make me concerned.

[sohel]

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