class Polygon {
	
	Vertex first, last; // linked circular list of vertices
	
	Polygon()
	{
		first = null;
		last = null;
	}
	
	// add point to the linked circular list
	// pre: first = null or v.next != null for all vertices v
	public void AddPoint(int x, int y)
	{
		Vertex v = new Vertex(x,y,first);
		if (first == null){
			first = v;
			last = v;
		}
		last.next = v;
		last = v;
	}
	
	public boolean IntersectHorizontalLeft(int x, int y, Vertex a, Vertex b)
	{
		if (a.y < y && y <= b.y || b.y < y && y <= a.y) // schnitt
		{
			double sx = a.x + (b.x-a.x) * (double) (y-a.y) / (b.y-a.y);
			return sx <= x; // Schnittpunkt links
		}
		else
			return false;
	}
	
	public boolean PointInPolygon(int px, int py)
	{
		if (first == last) // degeneriert 
			return false;
		else // first != last
		{
			int count = 0;
			Vertex v = first;
			do{ // Kante von v nach v.next;
				// zaehle Kanten mit echtem Schnitt
				if (IntersectHorizontalLeft(px, py, v, v.next))
				{	count ++;
				}
				v = v.next;
			} while (v != first);
			return count % 2 == 1;			
		}
	}
	

	
}