CSA Round #68 C Right Triangles

問題ページ
CS Academy

概要

2次元座標上のN点(x, y)が与えられる。各点について3点(x,y)(0,0)(x,0)を結んでできる三角形の内部に他のN-1点のうち何個が含まれているか求めろ

2 <= N <= 10^5
1 <= x,y <= 10^5
xは全て異なる
原点と(x,y)を結んだ線上に他の点は存在しない

考えたこと

• xが小さい順に点を並べておくとその点より前に出たy座標がより小さい点は三角形の内部に入ってる気持ちになる
• BITで数えればいい気持ちになる
• 冷静になって考えると嘘(サンプルが弱すぎる)
• どんな状況で点が三角形の内部に入るのか
• (x1, y1)がつくる三角形の中に(x2, y2)が入るときはx2 < x1, y1/x1 > y2/x2 になる
• 傾きでソートして前に出たx座標がより小さい点の数を数えるとよさそう
• BITでできるのでO(NlogN)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int bit[100010], m = 100010;

//0からi-1番目までの和
int sum(int i) {
  i++;
  int s = 0;
  while(i > 0) {
    s += bit[i];
    i -= i&-i;
  }
  return s;
}

//i番目(0-index)にxを加える
void add(int i, int x) {
  i++;
  while(i <= m) {
    bit[i] += x;
    i += i&-i;
  }
}

int dp[100010], x[100010], y[100010];
signed main(void)
{
  int n;
  cin >> n;
  vector<pair<double, int>> v;
  REP(i, n) {
    cin >> x[i] >> y[i];
    v.PB({(double)y[i]/x[i], i});
  }
  sort(ALL(v));

  dp[v[0].second] = 0;
  add(x[v[0].second], 1);
  FOR(i, 1, n) {
    dp[v[i].second] = sum(x[v[i].second]);
    add(x[v[i].second], 1);
  }

  REP(i, n) {
    cout << dp[i] << endl;
  }

  return 0;
}