Cod sursa(job #705402)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 4 martie 2012 11:04:06
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 10.13 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/hash_set>

#define MAXN 808
#define MAX_XY 60001

using namespace std;
using namespace __gnu_cxx;

typedef unsigned short uint16;

class Vector2D
{
public:
	Vector2D() :
		x(0),
		y(0)
	{}
	
	Vector2D(const int xx, const int yy) :
		x(xx),
		y(yy)
	{}
	
	inline double operator % (const Vector2D& v) const
	{
		return ((double)x * v.y) - ((double)y * v.x);
	}
	
	inline Vector2D operator - (const Vector2D& v) const
	{
		return Vector2D(x - v.x, y - v.y);
	}
	
	inline Vector2D operator + (const Vector2D& v) const
	{
		return Vector2D(x + v.x, y + v.y);
	}
	
	inline void operator -= (const Vector2D& v)
	{
		x -= v.x;
		y -= v.y;
	}
	
	inline void operator += (const Vector2D& v)
	{
		x += v.x;
		y += v.y;
	}

	int x,y;
};

class Segment
{
public:
	Segment()
	{}
	
	Segment(const Vector2D& s, const Vector2D& e) :
		midY(0.0f),
		start(s),
		end(e)
	{
		swapEndPoints();
	}
	
	Segment(const int x1, const int y1, const int x2, const int y2) :
			midY(0.0f),
			start(x1, y1),
			end(x2, y2)
	{
		swapEndPoints();
	}
	
	float midY;
	Vector2D start, end;

private:

	inline void swapEndPoints()
	{
		if (start.x > end.x)
		{
			swap(start, end);
		}
		else if (start.x == end.x)
		{
			if (start.y > end.y)
			{
				swap(start, end);
			}
		}
	}
};

inline bool ArePointsColinear
(
	const Vector2D& p1,
	const Vector2D& p2,
	const Vector2D& p3
)
{
	const Vector2D V1 = p2 - p1;
	const Vector2D V2 = p3 - p1;
	
	if ((V1 % V2) == 0)
	{
		return true;
	}
	
	return false;
}

inline bool SegmentProjectionContainsX(const Segment& seg, const int x)
{
	if (x >= seg.start.x && x <= seg.end.x)
	{
		return true;
	}
	
	return false;
}

inline bool SegmentsIntersect(const Segment& seg1, const Segment& seg2)
{
	const Vector2D V1 = seg1.end - seg1.start;
	const Vector2D V2 = seg2.end - seg2.start;
	
	const double crossV12 = V1 % V2;
	const double crossV21 = V2 % V1;
	
	const Vector2D diffSeg21_start = seg2.start - seg1.start;
	const Vector2D diffSeg12_start = seg1.start - seg2.start;
	
	const double crossDiffSeg21_V2 =  diffSeg21_start % V2;
	const double crossDiffSeg12_V1 = diffSeg12_start % V1;
	
	// check if lines are paralel
	if (0 == crossV12)
	{
		if (0 == crossDiffSeg21_V2) // check if lines are colinear
		{
			if (SegmentProjectionContainsX(seg1, seg2.start.x) ||
				SegmentProjectionContainsX(seg1, seg2.end.x))
			{
				return true;
			}
			
			if (SegmentProjectionContainsX(seg2, seg1.start.x) ||
				SegmentProjectionContainsX(seg2, seg1.end.x))
			{
				return true;
			}
		}
		
		return false;
	}
	
	//cout << crossDiffSeg21_V2 << " " << crossV12 << endl;
	
	const double u1 = static_cast<double>(crossDiffSeg21_V2) / crossV12;
	const double u2 = static_cast<double>(crossDiffSeg12_V1) / crossV21;
	
	//cout << u1 << " " << u2 << endl;
	
	if (u1 >= 0 && u1 <= 1 && u2 >= 0 && u2 <= 1)
	{
		return true;
	}
	
	return false;
}

inline bool ComparePointsByX(const Vector2D& p1, const Vector2D& p2)
{
	return p1.x < p2.x;
}

inline bool CompareSegmentsByStartX(const Segment& seg1, const Segment& seg2)
{
	return seg1.start.x < seg2.start.x;
}

inline bool CompareSegmentsByStartY(const Segment& seg1, const Segment& seg2)
{
	if (seg1.start.y > seg2.start.y)
	{
		return true;
	}
	else if (seg1.start.y == seg2.start.y)
	{
		return seg1.end.y > seg2.end.y;
	}
	
	return false;
}

inline bool CompareSegmentByMidY(const Segment& seg1, const Segment& seg2)
{
	return seg1.midY > seg2.midY;
}

inline float GetMidY(const Vector2D& p1, const Vector2D& p2, const int x)
{
	const float slope = ((float)(p2.y - p1.y)) / (p2.x - p1.x);
	
	return slope*(x-p1.x) + p1.y;
}

inline int GetCompactPoint(const int x, const int y)
{
	return ((x<<16) | y);
}

Vector2D vPoints[MAXN];
Segment vSegments[MAXN];

vector<Segment> vStrips[MAXN];
vector<Segment> vFringeSegments[MAXN];

hash_set<int> hsPoints;

inline int FindStrip(const int px, const int numStrips)
{
	int step = 1;
	while (step <= numStrips)
	{
		step <<= 1;
	}
	
	int i=0;
	for (i=0; step>0; step >>= 1)
	{
		if (i+step < numStrips && vPoints[i+step].x <= px)
		{
			i += step;
		}
	}
	
	if (i==0 && px < vPoints[0].x)
	{
		// We were to the left of the furthest left strip.
		// This means we're surely not inside the polygon.
		return -1;
	}
	else if (i==numStrips-1 && px > vPoints[numStrips-1].x)
	{
		// We were to the right of the furthest right strip.
		// This means we're surely not inside the polygon.
		return -2;
	}
	
	return i;
}

inline int GetNumberOfIntersections(const Segment& seg, const vector<Segment>& vSegments)
{
	int step = 1;
	const int size = vSegments.size();
	
	while (step <= size)
	{
		step <<= 1;
	}
	
	int i=0;
	for (i=0; step>0; step >>= 1)
	{
		if (i+step < size && SegmentsIntersect(seg, vSegments[i+step]))
		{
			i += step;
		}
	}
	
	if (size && seg.start.y <= vSegments[i].start.y)
    {
        return i;
    }
    
    return -1;
}

inline int GetFringeSegment(const Vector2D& p, const vector<Segment>& vFringeSegments)
{
    int step = 1;
    const int size = vFringeSegments.size();
    
    while (step <= size)
    {
        step <<= 1;
    }
    
    int i=0;
    for (i=0; step>0; step >>= 1)
    {
        if (i+step < size && p.y>=vFringeSegments[i+step].start.y && p.y<=vFringeSegments[i+step].end.y)
        {
            i += step;
        }
    }
    
    if (size && p.y>=vFringeSegments[i].start.y && p.y<=vFringeSegments[i].end.y)
    {
        return i;
    }
    
    return -1;
}

int main()
{
	int n, m, incedPoints=0;
	fstream fin("poligon.in", fstream::in);
	fstream fout("poligon.out", fstream::out);
	
	fin >> n >> m;
	//cout << n << " " << m << "\n";
	
	int x, y;
	fin >> x >> y;
	vPoints[0] = Vector2D(x,y);

	for (int i=1; i<n; ++i)
	{
		fin >> x >> y;
		
		hsPoints.insert(GetCompactPoint(x, y));

		vPoints[i] = Vector2D(x,y);
		vSegments[i-1] = Segment(vPoints[i-1], vPoints[i]);
	}
	vSegments[n-1] = Segment(vPoints[0], vPoints[n-1]);

	sort(vPoints, vPoints+n, &ComparePointsByX);
	sort(vSegments, vSegments+n, &CompareSegmentsByStartX);
	
	for (int i=0; i<n; ++i)
	{
		for (int j=0; vSegments[j].start.x <= vPoints[i].x && j<n; ++j)
		{
			if (vPoints[i].x < vSegments[j].end.x)
			{
				vSegments[i-1].midY = GetMidY(vSegments[i-1].start, vSegments[i-1].end, vPoints[i].x);
				vStrips[i].push_back(vSegments[j]);
			}
			else if (vPoints[i].x == vSegments[j].start.x && vPoints[i].x == vSegments[j].end.x)
			{
				vFringeSegments[i].push_back(vSegments[j]);
			}
		}
		
		sort(vStrips[i].begin(), vStrips[i].end(), &CompareSegmentsByStartY);
		sort(vFringeSegments[i].begin(), vFringeSegments[i].end(), &CompareSegmentByMidY);
	}

	
	/*for (int i=0; i<n; ++i)
	{
		cout << "(" << vPoints[i].x << " " << vPoints[i].y << ") -->  ";
		for (uint16 j=0; j<vStrips[i].size(); ++j)
		{
			cout << "(" << vStrips[i][j].start.x << " " << vStrips[i][j].start.y << " "
				 << vStrips[i][j].end.x << " " << vStrips[i][j].end.y << ")  ";
		}
		cout << "\n--> ";
        for (uint16 j=0; j<vFringeSegments[i].size(); ++j)
		{
			cout << "(" << vFringeSegments[i][j].start.x << " " << vFringeSegments[i][j].start.y << " "
				 << vFringeSegments[i][j].end.x << " " << vFringeSegments[i][j].end.y << ")  ";
		}
		cout << "\n\n";
	}*/
	
	for (int i=0; i<m; ++i)
	{
		fin >> x >> y;

		if (hsPoints.find(GetCompactPoint(x, y)) != hsPoints.end())
		{
			//cout << "Inside: Is a point\n";
			incedPoints++;
		}
		else
		{
			const Vector2D p(x,y);
			const int indexStrip = FindStrip(p.x, n);
			//cout << "Index = " << indexStrip;
			
			if (indexStrip >= 0)
			{
				const Segment rayPoint(p, Vector2D(p.x, MAX_XY));

				if (vPoints[indexStrip].x == p.x)
				{
					const int lineIndex = GetFringeSegment(p, vFringeSegments[indexStrip]);

					if (lineIndex == -1)
					{
						const int indexLastLine = GetNumberOfIntersections(rayPoint, vStrips[indexStrip]);
						
						if (indexLastLine >= 0)
						{
							if (ArePointsColinear(vStrips[indexStrip][indexLastLine].start, vStrips[indexStrip][indexLastLine].end, p))
							{
								//cout << "\nInside: 1) Point lies on very last line";
								incedPoints++;
							}
							else
							{
								//cout << ((indexLastLine+1)%2 ? "\nInside\n" : "\nOutside\n");
								if ((indexLastLine+1)%2 != 0)
								{
									incedPoints++;
								}
							}

							/*cout << "\n1) Last line index = " << indexLastLine << endl;
							cout << vStrips[indexStrip][indexLastLine].start.x << " " << vStrips[indexStrip][indexLastLine].start.y << endl;
							cout << vStrips[indexStrip][indexLastLine].end.x << " " << vStrips[indexStrip][indexLastLine].end.y << endl;*/
						}
					}
					else
					{
						//cout << "\nInside: Fringe Line Index = " << lineIndex << endl;
						incedPoints++;
					}
				}
				else
				{
					//cout << "  " << vPoints[indexStrip].x << " " << vPoints[indexStrip].y << endl;
					
					const int indexLastLine = GetNumberOfIntersections(rayPoint, vStrips[indexStrip]);
					
					if (indexLastLine >= 0)
					{
						if (ArePointsColinear(vStrips[indexStrip][indexLastLine].start, vStrips[indexStrip][indexLastLine].end, p))
						{
							//cout << "\nInside: 2) Point lies on very last line";
							incedPoints++;
						}
						else
						{
							//cout << ((indexLastLine+1)%2 ? "Inside\n" : "Outside\n");
							if ((indexLastLine+1)%2 != 0)
							{
								incedPoints++;
							}
						}

						/*cout << "\n2) Last line index = " << indexLastLine << endl;
						cout << vStrips[indexStrip][indexLastLine].start.x << " " << vStrips[indexStrip][indexLastLine].start.y << endl;
						cout << vStrips[indexStrip][indexLastLine].end.x << " " << vStrips[indexStrip][indexLastLine].end.y << endl;*/
					}
				}
			}
		}
	}
	
	fout << incedPoints << "\n";
	
	//cout << SegmentsIntersect(Segment(0,60000, 60000,60000), Segment(60000,0, 60000, 60001)) << endl;
	
	fin.close();
	fout.close();
	return 0;
}