Ali-ElMasry

Untitled

Sep 22nd, 2021
848
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<ll, ll> pll;
  7. typedef pair<int, int> pii;
  8.  
  9. #define endl "\n"
  10.  
  11. const ll INF = 1e15;
  12. const int MOD = 1e9 + 7;
  13. const double EPS = 1e-9;
  14. const double PI = acos(-1.0);
  15.  
  16. mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
  17.  
  18. const int N = 1005;
  19.  
  20. ll t, n, l, r;
  21. pll p[N];
  22.  
  23. pll slope(int i, int j) {
  24.     ll dx = p[j].first - p[i].first, dy = p[j].second - p[i].second;
  25.     if (!dx && !dy)
  26.         return {0, 0};
  27.     if (dx && dy) {
  28.         ll g = __gcd(llabs(dx), llabs(dy));
  29.         dx /= g, dy /= g;
  30.     }
  31.     if (dx == 0)
  32.         dy = 1;
  33.     else if (dy == 0)
  34.         dx = 1;
  35.     else if (dx < 0)
  36.         dx *= -1, dy *= -1;
  37.     return {dx, dy};
  38. }
  39.  
  40. pll perp(pll s) {
  41.     ll dx = -s.second, dy = s.first;
  42.     if (dx == 0)
  43.         dy = 1;
  44.     else if (dy == 0)
  45.         dx = 1;
  46.     else if (dx < 0)
  47.         dx *= -1, dy *= -1;
  48.     return {dx, dy};
  49. }
  50.  
  51. long double dist(int i, int j) {
  52.     ll dx = p[j].first - p[i].first, dy = p[j].second - p[i].second;
  53.     return sqrt(dx * dx + dy * dy);
  54. }
  55.  
  56. vector<pair<pll, long double>> have;
  57.  
  58. int main() {
  59.     ios::sync_with_stdio(false);
  60.     cin.tie(NULL), cout.tie(NULL);
  61.  
  62.     freopen("points.in", "r", stdin);
  63.  
  64.     cin >> t;
  65.  
  66.     while (t--) {
  67.         cin >> n >> l >> r;
  68.  
  69.         for (int i = 0; i < n; ++i)
  70.             cin >> p[i].first >> p[i].second;
  71.  
  72.         ll ans = 0;
  73.         for (int i = 0; i < n; ++i) {
  74.             for (int j = 0; j < n; ++j)
  75.                 have.emplace_back(slope(i, j), dist(i, j));
  76.             sort(have.begin(), have.end());
  77.  
  78.             for (auto& [s, h] : have) {
  79.                 if (s == pll {0, 0})
  80.                     continue;
  81.                 pll pp = perp(s);
  82.  
  83.                 ans += upper_bound(have.begin(), have.end(), make_pair(pp, r * 2.0 / h + EPS)) -
  84.                     lower_bound(have.begin(), have.end(), make_pair(pp, l * 2.0 / h - EPS));
  85.             }
  86.             have.clear();
  87.         }
  88.         cout << ans / 2 << endl;
  89.     }
  90. }
RAW Paste Data