fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Struktura reprezentująca punkt/wektor
  9. struct Point {
  10.     long long x, y;
  11. };
  12.  
  13. // Iloczyn wektorowy (cross product) wektorów OA i OB
  14. // Zwraca wartość dodatnią, ujemną lub 0
  15. long long cross_product(const Point& O, const Point& A, const Point& B) {
  16.     return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  17. }
  18.  
  19. // Funkcja sprawdzająca, czy punkt P znajduje się wewnątrz wielokąta wypukłego
  20. bool is_inside_polygon(const Point& P, const vector<Point>& poly) {
  21.     int n = poly.size();
  22.     // Sprawdzamy orientację względem pierwszego i ostatniego boku
  23.     if (cross_product(poly[0], poly[1], P) < 0) return false;
  24.     if (cross_product(poly[0], poly[n - 1], P) > 0) return false;
  25.  
  26.     // Wyszukiwanie binarne odpowiedniego segmentu kątowego
  27.     int low = 1, high = n - 1;
  28.     while (high - low > 1) {
  29.         int mid = (low + high) / 2;
  30.         if (cross_product(poly[0], poly[mid], P) >= 0) {
  31.             low = mid;
  32.         } else {
  33.             high = mid;
  34.         }
  35.     }
  36.     return cross_product(poly[low], poly[high], P) >= 0;
  37. }
  38.  
  39. // Komparator do sortowania kątowego wokół punktu P
  40. struct AngularCompare {
  41.     Point P;
  42.     AngularCompare(Point p) : P(p) {}
  43.  
  44.     // Funkcja pomocnicza określająca półpłaszczyznę (góra/dół)
  45.     int half_plane(const Point& q) const {
  46.         if (q.y == P.y) {
  47.             return q.x < P.x ? 1 : 0;
  48.         }
  49.         return q.y < P.y ? 1 : 0;
  50.     }
  51.  
  52.     bool operator()(const Point& a, const Point& b) const {
  53.         int hp_a = half_plane(a);
  54.         int hp_b = half_plane(b);
  55.         if (hp_a != hp_b) {
  56.             return hp_a < hp_b;
  57.         }
  58.         long long cp = (a.x - P.x) * (b.y - P.y) - (a.y - P.y) * (b.x - P.x);
  59.         return cp > 0; // Sortowanie przeciwnie do ruchu wskazówek zegara
  60.     }
  61. };
  62.  
  63. long long solve_for_point(int n, const vector<Point>& poly, const Point& P) {
  64.     // Jeśli punkt jest poza wielokątem, nie może być w żadnym trójkącie
  65.     if (!is_inside_polygon(P, poly)) {
  66.         return 0;
  67.     }
  68.  
  69.     // Tworzymy listę wierzchołków posortowaną kątowo względem P
  70.     vector<Point> pts = poly;
  71.     sort(pts.begin(), pts.end(), AngularCompare(P));
  72.  
  73.     // Dublujemy tablicę, aby łatwo symulować cykliczność (gąsienica)
  74.     for (int i = 0; i < n; i++) {
  75.         pts.push_back(pts[i]);
  76.     }
  77.  
  78.     long long bad_triangles = 0;
  79.     int j = 0;
  80.  
  81.     // Metoda dwóch wskaźników
  82.     for (int i = 0; i < n; i++) {
  83.         if (j <= i) j = i + 1;
  84.  
  85.         // Rozszerzamy okno gąsienicy tak długo, jak punkty leżą po jednej stronie prostej
  86.         while (j < i + n && cross_product(P, pts[i], pts[j]) > 0) {
  87.             j++;
  88.         }
  89.  
  90.         long long count = j - i - 1;
  91.         if (count >= 2) {
  92.             // Kombinacja symbolu Newtona: count po 2
  93.             bad_triangles += (count * (count - 1)) / 2;
  94.         }
  95.     }
  96.  
  97.     // Łączna liczba wszystkich trójkątów: n po 3
  98.     long long total_triangles = (1LL * n * (n - 1) * (n - 2)) / 6;
  99.  
  100.     return total_triangles - bad_triangles;
  101. }
  102.  
  103. int main() {
  104.     // Optymalizacja wejścia/wyjścia
  105.     ios_base::sync_with_stdio(false);
  106.     cin.tie(NULL);
  107.  
  108.     int n;
  109.     if (!(cin >> n)) return 0;
  110.  
  111.     vector<Point> poly(n);
  112.     for (int i = 0; i < n; i++) {
  113.         cin >> poly[i].x >> poly[i].y;
  114.     }
  115.  
  116.     // Upewniamy się, że wielokąt jest zorientowany przeciwnie do wskazówek zegara (CCW)
  117.     // Jeśli wejście jest CW (zgodnie z treścią zadania), odwracamy wektor
  118.     long long area = 0;
  119.     for (int i = 0; i < n; i++) {
  120.         int next = (i + 1) % n;
  121.         area += (poly[i].x * poly[next].y - poly[next].x * poly[i].y);
  122.     }
  123.     if (area < 0) {
  124.         reverse(poly.begin(), poly.end());
  125.     }
  126.  
  127.     int t;
  128.     if (cin >> t) {
  129.         while (t--) {
  130.             Point P;
  131.             cin >> P.x >> P.y;
  132.             cout << solve_for_point(n, poly, P) << "\n";
  133.         }
  134.     }
  135.  
  136.     return 0;
  137. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5
7 6
6 3
4 1
1 2
2 4
4
3 3
2 3
5 5
4 2
stdout
copy 
5
3
3
4
https://ideone.com/XcVPhU
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!