881 - Points, Polygons and Containers

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

881 - Points, Polygons and Containers

Post by Darko »

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[0];
		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
Location: Calgary, Canada

Post by Darko »

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
Location: Calgary, Canada

Post by Darko »

"Nice conversation there, Darko..."
"Thanks, Darko!" :D

Anyway, it works, problem was with some UVa Java stuff.

Post Reply

Return to “Volume 8 (800-899)”