Polygon

Modern graphic computer programs can, among other, even more stunningcapabilities, fill a closed region. Though not all of them can protect theuser from accidentally choosing to fill the background rather than the innerpart. Besides being a channel hopper at home your boss' favouritehobby is colouring the pictures, you cannot protest long about adding thismagnificent protection feature to his graphic program.

This means that your job is to write a program, which determines whether apoint belong to a polygon, given the array of its vertices.

To make life a bit simpler you may assume that:

• all edges of the polygon are vertical or horizontal segments
• lengths of all the edges of the polygon are even integer numbers
• co-ordinates of at least one vertex are odd integer numbers
• both co-ordinates of any vortex cannot be divisible by 7 at the same time
• the investigated point P has both co-ordinates being even integer numbers
• the polygon has at most 1000 vertices
• co-ordinates of the vertices lay in the range: -10000..10000.

Input 

Input data may consist of several data sets, each beginning with a numberof polygon's vertices (n). Consecutive n lines contain co-ordinates ofthe vertices (x followed by y). Then go the co-ordinates of investigatedpoint P. Input data end when you find 0 the number of polygon's vertices.

Output 

For each polygon and each point P you should print one character (inseparate lines): T when P belongs to the polygon or F otherwise.

Sample Input 

41 11 33 33 12 2121 11 93 93 55 55 97 97 15 15 33 33 14 20

Sample Output 

TF

---

Miguel A. Revilla
2000-01-10

利用射線法 - 判斷一個點是不是在一個簡單多邊形內。
判斷的方法 從那個點拉一條水平射線(往正向), 求交到多邊形的點個數。
偶數在多邊形外，奇數則在多邊內。 (核心代碼來自 DJWS)


#include <stdio.h>
struct Pt {
    double x, y;
};
int main() {
    int n, i, j;
    Pt p[1005], q;
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++)
            scanf("%lf %lf", &p[i].x, &p[i].y);
        scanf("%lf %lf", &q.x, &q.y);
        int cnt = 0;
        for(i = 0, j = n-1; i < n; j = i++) {
            if(p[i].y > q.y != p[j].y > q.y && // q.y in [pi.y, pj.y)
               q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y)+p[i].x)
            cnt++;
        }
        puts(cnt&1 ? "T": "F");
    }
    return 0;
}
/*
5
1 1
1 3
6 3
6 2
3 2
1.5 2
*/

---