Given a point A (x, y) and N segments (x1, y1, x2, y2). Check if these segments can enclose point A
Enclose = point A will stay in (or on any segment) a polygon made by endpoints of segments or their intersection points (sorry for my poor English)
Could anyone tell me how fast we can solve this problem, please?
N <= 150
coordinates <= abs(10^4)
Thanks
Point enclosed by segments
Moderator: Board moderators

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
As I understood the original problem, this won't work.
An O(n^2) solution should be reasonable. (Disregarding special cases,) test all pairs of segments for intersection, build a graph where vertices=intersections, edges=parts of segments. This graph is clearly planar.
Find the face that contains the point A and verify whether it is the outer face or not.
An O(n^2) solution should be reasonable. (Disregarding special cases,) test all pairs of segments for intersection, build a graph where vertices=intersections, edges=parts of segments. This graph is clearly planar.
Find the face that contains the point A and verify whether it is the outer face or not.
this is what USA computing olympiad training site says at their chapter 3.4
USACO 3.4 wrote:
Point in triangle
To check if a point A is in a triangle, find another point B which is within the triangle (the average of the three vertices works well). Then, check if the point A is on the same side of the three lines defined by the edges of the triangle as B.
Point in convex polygon
The same trick works for a convex polygon:
Checking convexity of 2dimensional polygon
To check the convexity of a 2dimensional polygon, walk the polygon in clockwise order. For each triplet of consecutive points (A, B, C), calculate the cross product (B  A) x (C  A). If the z component of each of these vectors is positive, the polygon is convex.
Point in nonconvex polygon
To calculate if a point is within a nonconvex polygon, make a ray from that point in a random direction and count the number of times it intersects the polygon. If the ray intersects the polygon at a vertex or along an edge, pick a new direction. Otherwise, the point is within the polygon if and only if the ray intersects the polygon an odd number of times.
This method also extends to three dimensions (and higher), but the restriction on intersection is that it only intersects at faces and not at either a vertex or an edge.
fahim
#include <smile.h>
#include <smile.h>