## 361 - Cops and Robbers

Moderator: Board moderators

### Yet WA

Well, after a while I was decided to try again this problem!

I am now a more experienced programmer and know more algorithms to help me, so, on this problem I thought that Jarvin's March and Point in Poly are the one's of choice, togheter with point in seg.

So, my approach was:

Code: Select all
`1. read in cops and robbers positions.2. find the convex hull for the cops and/or robs if more then 2 cops/robbers3. now, for each citizen:    4. if more then 2 cops:        5. if the citizen is in the same place of a cop or               the citizen is between two cops (on a line) or               the citizen is inside the convex hull            6. the citizen is said to be safe    7. else do the tests of 4 and 5 for the robs    9. if not safe and not robbed        10. the citizen is said to be neither`

And this gives me WA

Can anyone help, or should I surrender?

JP!
jpfarias
Learning poster

Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

I got accepted after ~50 trials, sice I've forgotten that if number of cops < 3, then no one can be safe. Similar thing applies to robbers.

(How I wish I had read Ivan Golubev's previous posts carefully )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

As I understand from this posts, following are correct:
INPUT:
3 0 4
0 0
0 0
10 0
0 0
5 0
10 0
11 0

4 0 2
-1 1
-1 1
-1 1
-1 1
10 10
-1 1
0 0 0
OUTPUT:
Data set 1:
Citizen at (0,0) is safe.
Citizen at (5,0) is safe.
Citizen at (10,0) is safe.
Citizen at (11,0) is neither.

Data set 2:
Citizen at (10,10) is neither.
Citizen at (-1,1) is safe.
According to the problem statement:
For purposes of this problem, a triangle consists of three non-collinear points
How can anybody be possibly safe in the first data set, if it does not contain triangles???????????
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Just got accepted from the second try... JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!JUDGE IS WRONG !!!

see previos post!!!!!!
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

No, but the postscript file is wrong.
The html version has a different definition of what a triangle is.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Per wrote:No, but the postscript file is wrong.
The html version has a different definition of what a triangle is.
The html version has been changed after I sent a email to the uva admin. When I was posting here, the html was wrong. (I dont even know how to open postscript on my windows...)

PS: it's good there is finally some competition for the first place in the rank list
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Previous