[UVA][凸凹形判斷] 10078 - The Art Gallery
Problem D
The Art Gallery
Input: standard input
Output: standard output
Century Arts has hundreds of art galleries scattered all around the country and you are hired to write a program that determines whether any of the galleries has a critical point. The galleries are polygonal in shape and a critical point is a point inside that polygon from where the entire gallery is not visible.
For example, in gallery 1 (drawn below) point A is a critical point, but gallery 2 has no critical point at all.
The Century Arts authorities will provide you with the shape of a gallery as a sequence of (x, y) co-ordinates (determined using a suitable origin) of the consecutive corner points of that gallery.
Input
The input file consists of several data blocks. Each data block describes one gallery.
The first line of a data block contains an integer N (3 £ N £ 50) indicating the number of corner points of the gallery. Each of the next N lines contains two integers giving the (x, y) co-ordinates of a corner point where 0 £ x, y £ 1000. Starting from the first point given in the input the corner points occur in the same order on the boundary of the gallery as they appear in the input. No three consecutive points are co-linear.
The input file terminates with a value of 0 for N.
Output
For each gallery in the input output the word "Yes" if the gallery contains a critical point, otherwise output the word "No". Each output must be on a separate line.
Sample Input
40 0
3 0
3 3
0 3
4
0 0
3 0
1 1
0 3
0
Sample Output
NoYes
已經給定順序給點, 檢查外積是不是全部為正, 或者是全部為負
#include <stdio.h>
typedef struct {
int x, y;
} Pt;
int cross(Pt o, Pt a, Pt b) {
return (a.x - o.x)*(b.y - o.y) -
(a.y - o.y)*(b.x - o.x);
}
int main() {
int n, i;
Pt D[100];
while(scanf("%d", &n), n) {
for(i = 0; i < n; i++)
scanf("%d %d", &D[i].x, &D[i].y);
D[n] = D[0], D[n+1] = D[1];
if(cross(D[0], D[1], D[2]) >= 0) {
for(i = 0; i < n; i++)
if(cross(D[i], D[i+1], D[i+2]) < 0)
break;
} else {
for(i = 0; i < n; i++)
if(cross(D[i], D[i+1], D[i+2]) > 0)
break;
}
if(i != n)
puts("Yes");
else
puts("No");
}
return 0;
}