[UVA][凸包、射線法] 11072 - Points
Points
Time limit: 10s
In this problem you will be given a set of points in the Euclidian plane. The number of points in the set will never exceed 100000. The coordinates of these points will be integer coordinates and will have an absolute value smaller than 10000. There will be no identical points in the first set. Then you will be given a second set of points. For each point in the second set you will have to determine whether it lies in a triangle spanned by three points in the first set. A point lying on the edge of a triangle is considered to be "inside" the triangle.
In the following example the points p1,p2,p3,p4 belong to
the first set. The points r and s belong to the second set. The point r isn't contained
in any triangle spanned by three points of the first set. The point s is contained in two triangles.
For example, the triangle spanned by p2,p3,p4.
Input
You will be given several testcases. A testcases consists of the number of points p, 3 ≤ p ≤ 100000 in the first set. It is followed by p pairs of numbers, each describing a point of the first set, the first number of a pair denoting the x-coordinate of the point, the second the y-coordinate. Each pair is on a seperate line. There may be colinear points in the first set. The next number in the input gives you the number of points r in the second set. It is followed by r pairs of numbers, each describing a point, each on a separate line. The first number of a pair being the x-coordinate, the second number being the y-coordinate of the point. All coordinates in the input will be integer coordinates.Output
For each point in the second set, output if the point lies in a triangle spanned by three points of the first set. If the point lies inside a triangle output inside otherwise output outside.Sample input
4 0 0 4 4 0 4 4 0 6 2 2 4 4 1 1 0 2 0 10 10 0
Sample output
inside inside inside inside outside outside
FAU Local Summer Contest 2005
Author: Tilmann Spiegelhauer
題目描述：
給平面上一堆點，接著詢問一些點，這些點能不能在原本給定的點中挑出三點構成的三角形內部。
題目解法：
做一次凸包即可，凸包上任三點一定會包括所有情況的三角形，之後使用射線法求是否在凸包內部。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
double x, y;
Pt(double a = 0, double b = 0):
x(a), y(b) {}
bool operator <(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y < a.y;
}
bool operator ==(const Pt &a) const {
return x == a.x && y == a.y;
}
};
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double 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 monotone(int n, Pt p[], Pt ch[]) {
sort(p, p+n);
int i, m = 0, t;
for(i = 0; i < n; i++) {
while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
for(i = n-1, t = m+1; i >= 0; i--) {
while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
return m-1;
}
bool onSegment(Pt p, Pt s, Pt e) {
if(p == s || p == e) return 1;
return cross(p, s, e) == 0
&& dot(Pt(s.x-p.x, s.y-p.y), Pt(e.x-p.x, e.y-p.y)) < 0;
}
int inPolygon(Pt p[], int n, Pt q) {
int i, j, cnt = 0;
for(i = 0, j = n-1; i < n; j = i++) {
if(onSegment(q, p[i], p[j]))
return 1;
if(p[i].y > q.y != p[j].y > q.y &&
q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
cnt++;
}
return cnt&1;
}
Pt D[100005], C[100005<<1], p;
int main() {
for(int n; scanf("%d", &n) == 1;) {
int i, j, k;
for(i = 0; i < n; i++)
scanf("%lf %lf", &D[i].x, &D[i].y);
int cn = monotone(n, D, C);
int m;
scanf("%d", &m);
while(m--) {
scanf("%lf %lf", &p.x, &p.y);
puts(inPolygon(C, cn, p) ? "inside" : "outside");
}
}
return 0;
}