Fussy Sakamoto 思维+树状数组

https://ac.nowcoder.com/acm/problem/23931

题意

有很多坐标 x唯一
以(0,0) (x,0)(x,y) 形成直角三角形
问每个三角形出现的时候包含了多少前面出现的三角形考虑先后

思路

首先考虑包含的条件

1. 斜边一定要在当前三角形的下面用数据比较直观就是 y/x 斜率就可以表示那就是斜率要小于当前三角形的斜边斜率。
2. x轴要比当前三角形小不然包不住

这时候根据这两个条件排序之后又会出现新的问题因为优先斜率排序那么斜率小x大的也会排在前面就要根据x来看比x小的有多少个 暴力的话每次查询操作复杂度都是 O(n) 而树状数组可以做到 O(\log n) 这时候就要运用树状数组来解决这个问题。

#include <bits/stdc++.h>
using namespace std;

int a[200005];
int ans[100005];

struct node {
	double tan;
	int x;
	int pos;
} tree[100005];

bool cmp(node x, node y) {
	if (x.tan != y.tan) {
		return x.tan < y.tan;
	} else {
		return x.x < y.x;
	}
}

int lowbit(int x) {
	return x & -x;
}

void add(int i, int x) {
	while (i < 200005) {
		a[i] += x;
		i += lowbit(i);
	}
}

int query(int i) {
	int ans = 0;
	while (i) {
		ans += a[i];
		i -= lowbit(i);
	}
	return ans;
}

int main() {
	int x;
	while (cin >> x) {
		memset(a, 0, sizeof(a));
		for (int i = 0 ; i < x; i++) {
			int xx, yy;
			cin >> xx >> yy;
			tree[i].tan = yy * 1.0 / xx;
			tree[i].x = xx;
			tree[i].pos = i;
		}
		sort(tree, tree + x, cmp);
		for (int i = 0; i < x; i++) {
			int id = tree[i].pos;
			ans[id] = query(tree[i].x);
			add(tree[i].x, 1);
		}
		for (int i = 0; i < x; i++) {
			cout << ans[i] << endl;
		}
	}
}

In the math class, the teacher made a difficult question:
There are given N points having positive coordinates.
It is guaranteed all the points have distinct x coordinates and there are no two points that are collinear with the origin.
For each point having coordinates (x,y) consider the right triangle formed by:
the point itself: (x,y)
the origin of the coordinate system: (0,0)
the point’s projection on the x-axis: (x,0).
Ask how many of the other N−1 points the triangle which is formed by the first point contains.
Sakamoto is fussy so he thinks this problem is too simple, so he wants to solve a new problem.
For each triangle count how many of the other N-1 points it contains.
Constraints
2<=N<=1e5
The coordinates of the points are between 1 and 1e5.
there are no more than 5 data sets.