HUST 1376 Random intersection

Description

There are N segments on the plane. You are to find out how many pairs of segments intersect with each other. A pair of segments intersect with each other if and only if they have at least one common point.

Input

the first line contains a single integer T -- the number of the testcases then T testcases are followed each testcase contains an integer N( N <= 100000), the number of segments then N lines are followed, each line contains 4 floating point numbers: x1 y1 x2 y2 which means the coordinates of the two ends of a segment for more details, see the sample input (the input data is generated randomly, and the probability of a pair of segments intersecting is about 0.001)

Output

for each testcase, print 1 line with the number of the pairs of segments intersect with each other.

Sample Input

3
3
0.0000 0.0000 1.0000 2.0000
0.0000 1.0000 1.0000 0.0000
0.0000 2.0000 1.0000 1.0000
4
0.0000 0.0000 0.0000 -1.0000
0.0000 0.0000 1.0000 0.0000
0.0000 0.0000 0.0000 1.0000
0.0000 0.0000 -1.0000 0.0000
2
0.0000 0.0000 1.0000 1.0000
0.0000 0.0000 2.0000 2.0000

Sample Output

2
6
1

丧心病狂的题，能想到的只有暴力，然而单纯的暴力是不行的。

像线段树的扫描线一样做，把线段的端点标上号然后排序，只有在左右端点中间的点才可能和线段有交点。

然后暴力的判断就可以了，需要注意的是端点可能会有重合，需要特判一下。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e5 + 10;
int T, n;

struct point
{
  double x, y;
  int id;
  void read(int z){ id = z; scanf("%lf%lf", &x, &y); }
  bool operator==(const point&a)const{ return x == a.x&&y == a.y; }
  bool operator<(const point&a)const{ return x == a.x ? y < a.y : x < a.x; }
}L[maxn], R[maxn], a[maxn * 2];

double mult(point a, point b, point c)
{
  return (a.x - c.x)*(b.y - c.y) - (b.x - c.x)*(a.y - c.y);
}

bool check(point aa, point bb, point cc, point dd)
{
  if (aa == cc&bb == dd) return true;
  if (max(aa.x, bb.x)<min(cc.x, dd.x)) return false;
  if (max(aa.y, bb.y)<min(cc.y, dd.y)) return false;
  if (max(cc.x, dd.x)<min(aa.x, bb.x)) return false;
  if (max(cc.y, dd.y)<min(aa.y, bb.y)) return false;
  if (mult(cc, bb, aa)*mult(bb, dd, aa)<0) return false;
  if (mult(aa, dd, cc)*mult(dd, bb, cc)<0) return false;
  return true;
}

int main()
{
  cin >> T;
  while (T--)
  {
    scanf("%d", &n);
    for (int i = 1; i <=n; i++)
    {
      L[i].read(i); R[i].read(i);
      if (R[i] < L[i]) swap(L[i], R[i]);
      a[i * 2 - 1] = L[i];
      a[i * 2] = R[i];
      a[i * 2].id = -i;
    }
    sort(a + 1, a + n + n + 1);
    LL ans = 0;
    for (int i = 1; i <= n + n; i++)
    {
      if (a[i].id > 0)
      {
        int j;
        for (j = i + 1; -a[j].id != a[i].id; j++)
        {
          if (a[j].id > 0 && check(L[a[i].id], R[a[i].id], L[a[j].id], R[a[j].id])) ans++;
        }
        for (j++; a[j] == a[j - 1]; j++)
        if (a[j].id > 0 && check(L[a[i].id], R[a[i].id], L[a[j].id], R[a[j].id])) ans++;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}