题意:就是CF round# 329 B 的升级版,要求出相交点的个数
分析:逆序数用树状数组维护,求出非逆序数,然后所有情况(n * (n - 1)) / 2减之就是逆序数个数。
#include <bits/stdc++.h>
using namespace std; const int N = 1e4 + 10;
const double EPS = 1e-8; double x[N][2], y[N][2];
pair<double, double> a[N];
double A[N]; struct BIT {
int c[N], sz;
void init(int n) {
sz = n;
memset (c, 0, sizeof (c));
}
void updata(int i, int x) {
while (i <= sz) {
c[i] += x; i += i & (-i);
}
}
int query(int i) {
int ret = 0;
while (i) {
ret += c[i]; i -= i & (-i);
}
return ret;
}
}bit; int dcmp(double x) {
if (fabs (x) < EPS) return 0;
else return x < 0 ? -1 : 1;
} double cross(int i, double X) {
// if (dcmp (x[i][0] - x[i][1]) == 0) return 0;
double k = y[i][1] - y[i][0];
k /= (x[i][1] - x[i][0]);
double b = -k * x[i][0] + y[i][0];
return k * X + b;
} int main(void) {
int n;
while (scanf ("%d", &n) == 1) {
for (int i=0; i<n; ++i) {
scanf ("%lf%lf%lf%lf", &x[i][0], &y[i][0], &x[i][1], &y[i][1]);
}
double L, R; scanf ("%lf%lf", &L, &R);
L += EPS; R -= EPS;
for (int i=0; i<n; ++i) {
a[i].first = cross (i, L);
a[i].second = cross (i, R);
cout << a[i].first << " " << a[i].second << endl;
}
sort (a, a+n);
for (int i=0; i<n; ++i) A[i] = a[i].second;
sort (A, A+n);
int tot = unique (A, A+n) - A;
bit.init (n);
int ans = 0;
for (int i=0; i<n; ++i) {
int pos = lower_bound (A, A+tot, a[i].second) - A + 1;
ans += bit.query (pos);
bit.updata (pos, 1);
}
printf ("%d\n", n * (n - 1) / 2 - ans);
} return 0;
}