qbxt DAY7 T4

qbxt DAY7 T4

容易知道答案的横坐标就是所有横坐标的中位数，纵坐标也是（可以画图看一下）

暴力的思想就是求出所有的交点，然后找中位数，用nth_element可以(n^2)做

考虑到对于所有求出的交点，实际上只有中位数是有作用的，所以可以想如何优化这一部分

发现对于每一个交点，它产生的原因实际上是两条直线的相对位置变化，即一条在下面的直线到了另一条原本在他上面的直线的上面。如果我们把这些直线在负无穷处的位置按照高度进行排序，则每产生一个交点，相当于产生了一个逆序对。

这也就意味着，对于一个给定的(mid)，我们可以通过 check 逆序对的数量来判断这个点左边有多少个点。

那么这道题就可以通过二分查找逆序对来找到中位数的位置

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N = 40005;
int n, v[N];
int low(int x){return x & (-x);}
int query(int x)
{
	int ans = 0;
	for(; x; x -= low(x))
		ans += v[x];
	return ans;
}
void modify(int x){for(;x <= n; x += low(x)) v[x] ++;}
struct node
{
	db a, b, c;
}s[N];
bool cmp(node a, node b)
{
	return a.a / a.b < b.a / b.b;//按直线高度排序 
}
pair<db, int> f[N];
db ex = 0.00000001;//精度 
db solve()
{
	sort(s + 1, s + n + 1, cmp);
	db l = -2e8, r = 2e8;
	while(l < r && r - l > ex) 
	{
		db mid = (l + r) / 2;
		for(int i = 1; i <= n; i ++) f[i] = make_pair((s[i].c - mid * s[i].a) / s[i].b, i);
		sort(f + 1, f + n + 1);
		for(int i = 1; i <= n; i ++) v[i] = 0;
		ll res = 0;//求逆序对 
		for(int i = 1; i <= n; i ++)
		{
			res += i - 1 - query(f[i].second);
			modify(f[i].second);
		}
		if(res * 2 < n * (n - 1ll) / 2) l = mid;
		else r = mid;
	}
	return l;
}
int main()
{
	scanf("%d", &n);
	for(int i = 1, a, b, c; i <= n; i ++)
	{
		scanf("%d%d%d", &a, &b, &c);
		s[i].a = 1.0 * a, s[i].b = 1.0 * b, s[i].c = 1.0 * c;
	}
	printf("%.6lf ", solve());
	for(int i = 1; i <= n; i ++) swap(s[i].a, s[i].b);
	printf("%.6lf", solve());
	return 0;
 }