API tools faq
paste
Advertisement
tepyotin2

8.2 Cow Curling

tepyotin2
Jul 3rd, 2025
86
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.49 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Point {
  6.     long long x, y;
  7. };
  8.  
  9. Point operator-(Point a, Point b) {
  10.     return {a.x - b.x, a.y - b.y};
  11. }
  12.  
  13. long long cross_product(Point p1, Point p2, Point p3) {
  14.     return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
  15. }
  16.  
  17. vector<Point> convex_hull(vector<Point> points) {
  18.     int n = points.size();
  19.     if (n <= 2) return points;
  20.  
  21.     sort(points.begin(), points.end(), [](Point a, Point b) {
  22.         if (a.x != b.x) return a.x < b.x;
  23.         return a.y < b.y;
  24.     });
  25.  
  26.     vector<Point> lower_hull, upper_hull;
  27.     for (const auto& p : points) {
  28.         while (lower_hull.size() >= 2 && cross_product(lower_hull[lower_hull.size()-2], lower_hull.back(), p) <= 0) {
  29.             lower_hull.pop_back();
  30.         }
  31.         lower_hull.push_back(p);
  32.     }
  33.  
  34.     for (int i = n - 1; i >= 0; --i) {
  35.         const auto& p = points[i];
  36.         while (upper_hull.size() >= 2 && cross_product(upper_hull[upper_hull.size()-2], upper_hull.back(), p) <= 0) {
  37.             upper_hull.pop_back();
  38.         }
  39.         upper_hull.push_back(p);
  40.     }
  41.  
  42.     lower_hull.pop_back();
  43.     upper_hull.pop_back();
  44.     lower_hull.insert(lower_hull.end(), upper_hull.begin(), upper_hull.end());
  45.     return lower_hull;
  46. }
  47.  
  48. bool is_inside_hull(const vector<Point>& hull, Point p) {
  49.     int h = hull.size();
  50.     if (h < 3) return false;
  51.  
  52.     if (cross_product(hull[0], hull[1], p) < 0 || cross_product(hull[0], hull[h - 1], p) > 0) {
  53.         return false;
  54.     }
  55.  
  56.     int low = 1, high = h - 2;
  57.     int target_idx = -1;
  58.     while(low <= high) {
  59.         int mid = low + (high - low) / 2;
  60.         if (cross_product(hull[0], hull[mid], p) >= 0) {
  61.             target_idx = mid;
  62.             low = mid + 1;
  63.         } else {
  64.             high = mid - 1;
  65.         }
  66.     }
  67.  
  68.     if (target_idx == -1) return false;
  69.     return cross_product(hull[target_idx], hull[target_idx + 1], p) >= 0;
  70. }
  71.  
  72.  
  73. int calculate_score(vector<Point>& team_stones, vector<Point>& opponent_stones) {
  74.     if (team_stones.size() < 3) {
  75.         return 0;
  76.     }
  77.  
  78.     vector<Point> hull = convex_hull(team_stones);
  79.  
  80.     if (hull.size() < 3) {
  81.         sort(team_stones.begin(), team_stones.end(), [](Point a, Point b) {
  82.             if (a.x != b.x) return a.x < b.x;
  83.             return a.y < b.y;
  84.         });
  85.         Point p1 = team_stones.front();
  86.         Point p2 = team_stones.back();
  87.  
  88.         int score = 0;
  89.         for (const auto& stone : opponent_stones) {
  90.             if (cross_product(p1, p2, stone) == 0) {
  91.                 if (stone.x >= p1.x && stone.x <= p2.x &&
  92.                     stone.y >= min(p1.y, p2.y) && stone.y <= max(p1.y, p2.y)) {
  93.                     score++;
  94.                 }
  95.             }
  96.         }
  97.         return score;
  98.     }
  99.  
  100.     int score = 0;
  101.     for (const auto& opponent_stone : opponent_stones) {
  102.         if (is_inside_hull(hull, opponent_stone)) {
  103.             score++;
  104.         }
  105.     }
  106.     return score;
  107. }
  108.  
  109. int main() {
  110.     ios_base::sync_with_stdio(false);
  111.     cin.tie(NULL);
  112.  
  113.     freopen("curling.in", "r", stdin);
  114.     freopen("curling.out", "w", stdout);
  115.  
  116.     int n;
  117.     cin >> n;
  118.  
  119.     vector<Point> team_a(n), team_b(n);
  120.     for (int i = 0; i < n; ++i) cin >> team_a[i].x >> team_a[i].y;
  121.     for (int i = 0; i < n; ++i) cin >> team_b[i].x >> team_b[i].y;
  122.  
  123.     int score_a = calculate_score(team_a, team_b);
  124.     int score_b = calculate_score(team_b, team_a);
  125.  
  126.     cout << score_a << " " << score_b << endl;
  127.  
  128.     return 0;
  129. }
  130.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!