Advertisement
hax33l

Problem_A_v2

May 20th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. struct Punkt {
  7.     int x; int y;
  8. };
  9.  
  10. bool max_test(int minx, int maxx, int miny, int maxy, int pktx, int pkty) {
  11.     return (pktx < minx || pktx >maxx || pkty < miny || pkty > maxy) ? true : false;
  12. }
  13.  
  14. bool pointOnLine(Punkt linePointA, Punkt linePointB, float testx,float testy)
  15. {
  16.     return (linePointB.x*testy+linePointA.x*linePointB.y+testx*linePointA.y-linePointA.x*testy-linePointB.x*linePointA.y-testx*linePointB.y==0 &&
  17.         testx>=min(linePointA.x,linePointB.x) && testx <=max(linePointA.x,linePointB.x) && testy>=min(linePointA.y,linePointB.y) && testy<=max(linePointA.y,linePointB.y))
  18.     ? true : false;
  19. }
  20.  
  21. bool pinpol(int nvert, Punkt * poly, float testx, float testy) {
  22.     int i, j;
  23.     bool c = false;
  24.     for (i = 0, j = nvert - 1; i < nvert; j = i++) {
  25.         if (((poly[i].y > testy) != (poly[j].y > testy)) &&
  26.             (testx < (poly[j].x - poly[i].x)*(testy - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x))
  27.             c = !c;
  28.     }
  29.     if (!c) {
  30.         for (int i = 0; i < nvert; i++) {
  31.             c = pointOnLine(poly[i], poly[i + 1], testx, testy);
  32.             if (c)
  33.                 break;
  34.         }
  35.     }
  36.     return c;
  37. }
  38.  
  39. int main() {
  40.     int zestawy_danych = 0, liczba_wierzcholkow = 0, liczba_punktow = 0, minx = 0, miny = 0, maxx = 0, maxy = 0,counter=0;
  41.     Punkt * wielokat;
  42.     Punkt * punkty;
  43.     cin >> zestawy_danych;
  44.     for (int i = 0; i < zestawy_danych; i++) {
  45.         minx = 0;
  46.         miny = 0;
  47.         maxx = 0;
  48.         maxy = 0;
  49.         counter = 0;
  50.         cin >> liczba_wierzcholkow >> liczba_punktow;
  51.         wielokat = new Punkt[liczba_wierzcholkow];
  52.         punkty = new Punkt[liczba_punktow];
  53.         for (int q = 0; q < liczba_wierzcholkow; q++) {
  54.             cin >> wielokat[q].x >> wielokat[q].y;
  55.             if (wielokat[q].x > maxx)
  56.                 maxx = wielokat[q].x;
  57.             if (wielokat[q].x < minx)
  58.                 minx = wielokat[q].x;
  59.             if (wielokat[q].y > maxy)
  60.                 maxy = wielokat[q].y;
  61.             if (wielokat[q].y < miny)
  62.                 miny = wielokat[q].y;
  63.         }
  64.         for (int q = 0; q < liczba_punktow; q++) {
  65.             cin >> punkty[q].x >> punkty[q].y;
  66.             if (max_test(minx, maxx, miny, maxy, punkty[q].x, punkty[q].y)) {
  67.                 continue;
  68.             }
  69.             else {
  70.                 if (pinpol(liczba_wierzcholkow, wielokat, punkty[q].x, punkty[q].y))
  71.                     counter++;
  72.             }
  73.         }
  74.         cout << counter << endl;
  75.     }
  76.     system("pause");
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement