Point enclosed by segments

[FAQ]

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
co-ordinates <= abs(10^4)

Thanks

[bugzpodder]

essentially you want to find a ray that goes between your point and end point of another line segment to see if it intersects any other line segments. if no then report no, otherwise report yes.

[misof]

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.

[FAQ]

excuse me misof,

I couldn't get this sentence

Find the face that contains the point A and verify whether it is the outer face or not.

how fast can we find a face like this?

[smilitude]

this is what USA computing olympiad training site says at their chapter 3.4

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 2-dimensional polygon
To check the convexity of a 2-dimensional polygon, walk the polygon in clock-wise 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 non-convex 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.