Points Within
Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 2222 Accepted Submit: 566
Statement of the Problem
Several drawing applications allow us to draw polygons and almost all of them allow us to fill them with some color. The task of filling a polygon reduces to knowing which points are inside it, so programmers have to colour only those points.
You're expected to write a program which tells us if a given point lies inside a given polygon described by the coordinates of its vertices. You can assume that if a point is in the border of the polygon, then it is in fact inside the polygon.
Input Format
The input file may contain several instances of the problem. Each instance consists of: (i) one line containing integers N, 0 < N < 100 and M, respectively the number of vertices of the polygon and the number of points to be tested. (ii) N lines, each containing a pair of integers describing the coordinates of the polygon's vertices; (iii) M lines, each containing a pair of integer coordinates of the points which will be tested for "withinness" in the polygon.
You may assume that: the vertices are all distinct; consecutive vertices in the input are adjacent in the polygon; the last vertex is adjacent to the first one; and the resulting polygon is simple, that is, every vertex is incident with exactly two edges and two edges only intersect at their common endpoint. The last instance is followed by a line with a 0 (zero).
Output Format
For the ith instance in the input, you have to write one line in the output with the phrase "Problem i:", followed by several lines, one for each point tested, in the order they appear in the input. Each of these lines should read "Within" or "Outside", depending on the outcome of the test. The output of two consecutive instances should be separated by a blank line.
Sample Input
3 1
0 0
0 5
5 0
10 2
3 2
4 4
3 1
1 2
1 3
2 2
0
Sample Output
Problem 1:
Outside
Problem 2:
Outside
Within
Problem Source: South America 2001
Analysis
Algorithm:
This problem is simple to understand. In order to determine the given point whether it is inner, initially, we should exclude the situation of the online occurrence. Be careful of the points which is an component of the polygon. And later, draw a directed line randomly and count the crossing points. If it is even, it is obviously inner and true for another situation: the point is outside when the result is odd.
code
#include <iostream>
using namespace std;
struct point
{
int x, y;
};
struct line{
point p1, p2;
};
const int MAXN = 101;
const int MAX = 99999999;
point p[MAXN];
int m, n;
inline int max(line l){
return (l.p1.y > l.p2.y ? l.p1.y : l.p2.y);
}
inline int min(line l){
return (l.p1.y > l.p2.y ? l.p2.y : l.p1.y);
}
inline int xmult(int x1, int y1, int x2, int y2){
return x1 * y2 - x2 * y1;
}
inline int pmult(int x1, int y1, int x2, int y2){
return x1 * x2 + y1 * y2;
}
inline int cmp(int x){
if (x == 0) return 0;
if (x < 0) return -1;
if (x > 0) return 1;
}
inline int cross(point a, point b, point c){
return cmp(xmult(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y));
}
inline int linecross(line l1, line l2){
return (cross(l1.p1, l2.p1, l2.p2) * cross(l1.p2, l2.p1, l2.p2) < 0
&& cross(l2.p1, l1.p1, l1.p2) * cross(l2.p2, l1.p1, l1.p2) < 0);
}
int test(point tp){
line poly, t;
int x = 0;
t.p1 = tp; t.p2.x = 1280213; t.p2.y = 321123;
for (int i = 0; i != n; ++i){
if (i == n - 1){
poly.p1 = p[n - 1]; poly.p2 = p[0];
} else {
poly.p1 = p[i]; poly.p2 = p[i + 1];
}
while(online(poly.p1,t.p1,t.p2)||online(poly.p2,t.p1,t.p2)) {t.p2.x++;t.p2.y++;}
if (linecross(poly, t)) ++x;
}
if (x % 2) return 1; else return 0;
}
int online(point tp, point a, point b){
if (cmp(xmult(tp.x - a.x, tp.y - a.y, b.x - a.x, b.y - a.y)) == 0 &&
cmp(pmult(tp.x - a.x, tp.y - a.y, tp.x - b.x, tp.y - b.y)) < 0 ) return 1; else return 0;
}
int checkonline(point tp){
for (int i = 0; i != n; ++i){
if (tp.x == p[i].x && tp.y == p[i].y) return 1;
}
for (int i = 0; i != n - 1; ++i){
if (online(tp, p[i], p[i + 1])) return 1;
}
if (online(tp, p[n - 1], p[0])) return 1; else return 0;
}
int main(){
int cases = 0;
point tp;
while (cin >> n && n != 0){
cin >> m;
++cases;
if (cases != 1) cout << endl;
for (int i = 0; i != n; ++i) cin >> p[i].x >> p[i].y;
cout << "Problem " << cases << ":" << endl;
for (int i = 0; i != m; ++i){
cin >> tp.x >> tp.y;
if (checkonline(tp)){
cout << "Within" << endl;
continue;
}
if (test(tp)) cout << "Within" << endl; else cout << "Outside" << endl;
}
}
return 0;
}