## 881 - Points, Polygons and Containers

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### 881 - Points, Polygons and Containers

http://acm.uva.es/p/v8/881.html

I think this should work: Sort polygons by area, start checking for point inside polygon, once found - print the number of the polygon, otherwise print 0.

I can't figure out what I might be missing or what to try next. Any suggestions?

Darko

P.S. Here's my point inside polygon function - points array contains n+1 points (first and last are the same):

Code: Select all

``````public boolean inside(Point881 p) {
Point881 p1, p2;
int count = 0;
p1 = points;
for (int k = 1; k < points.length; k++) {
p2 = points[k];
if (p1.y > p2.y || (p1.y == p2.y && p1.x > p2.x)) {
Point881 tmp = p1;
p1 = p2;
p2 = tmp;
}
if (p.y > p1.y && p.y <= p2.y) {
if (p.x < p1.x && p.x < p2.x) {
count++;
} else {
if ((p.y - p1.y) * (p2.x - p1.x) > (p2.y - p1.y)
* (p.x - p1.x))
count++;
}
}
p1 = points[k];
}
if ((count & 1) == 0)
return false;
else
return true;
}
``````

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Well, I went back to this one, played around with EPS values, but still WA.

Can someone tell me if my approach is OK at least? I am missing something, but not sure what.

Darko

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
"Thanks, Darko!" 