Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- struct Punkt {
- int x; int y;
- };
- bool max_test(int minx, int maxx, int miny, int maxy, int pktx, int pkty) {
- return (pktx < minx || pktx >maxx || pkty < miny || pkty > maxy) ? true : false;
- }
- bool pointOnLine(Punkt linePointA, Punkt linePointB, float testx,float testy)
- {
- return (linePointB.x*testy+linePointA.x*linePointB.y+testx*linePointA.y-linePointA.x*testy-linePointB.x*linePointA.y-testx*linePointB.y==0 &&
- testx>=min(linePointA.x,linePointB.x) && testx <=max(linePointA.x,linePointB.x) && testy>=min(linePointA.y,linePointB.y) && testy<=max(linePointA.y,linePointB.y))
- ? true : false;
- }
- bool pinpol(int nvert, Punkt * poly, float testx, float testy) {
- int i, j;
- bool c = false;
- for (i = 0, j = nvert - 1; i < nvert; j = i++) {
- if (((poly[i].y > testy) != (poly[j].y > testy)) &&
- (testx < (poly[j].x - poly[i].x)*(testy - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x))
- c = !c;
- }
- if (!c) {
- for (int i = 0; i < nvert; i++) {
- c = pointOnLine(poly[i], poly[i + 1], testx, testy);
- if (c)
- break;
- }
- }
- return c;
- }
- int main() {
- int zestawy_danych = 0, liczba_wierzcholkow = 0, liczba_punktow = 0, minx = 0, miny = 0, maxx = 0, maxy = 0,counter=0;
- Punkt * wielokat;
- Punkt * punkty;
- cin >> zestawy_danych;
- for (int i = 0; i < zestawy_danych; i++) {
- minx = 0;
- miny = 0;
- maxx = 0;
- maxy = 0;
- counter = 0;
- cin >> liczba_wierzcholkow >> liczba_punktow;
- wielokat = new Punkt[liczba_wierzcholkow];
- punkty = new Punkt[liczba_punktow];
- for (int q = 0; q < liczba_wierzcholkow; q++) {
- cin >> wielokat[q].x >> wielokat[q].y;
- if (wielokat[q].x > maxx)
- maxx = wielokat[q].x;
- if (wielokat[q].x < minx)
- minx = wielokat[q].x;
- if (wielokat[q].y > maxy)
- maxy = wielokat[q].y;
- if (wielokat[q].y < miny)
- miny = wielokat[q].y;
- }
- for (int q = 0; q < liczba_punktow; q++) {
- cin >> punkty[q].x >> punkty[q].y;
- if (max_test(minx, maxx, miny, maxy, punkty[q].x, punkty[q].y)) {
- continue;
- }
- else {
- if (pinpol(liczba_wierzcholkow, wielokat, punkty[q].x, punkty[q].y))
- counter++;
- }
- }
- cout << counter << endl;
- }
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement