题意
给你n条与坐标轴平行的线段，问有几个交点。数据保证没有重合的、长度为0的线段，没有共起点共终点的线段。
思路
由于所有线段都是和坐标轴平行的，所以可以把与x轴平行的线段和y轴平行的线段分开来看，将横着的线段纵坐标插入树状数组中，求所有竖着的线段起点到终点的区间和即为答案。求解的过程需要按照横坐标从小到大排序，横线段的点优先。
由于题目说明点的坐标绝对值是小于1e9的，需要将纵坐标离散化。可以使用stl中的sort，unique和lower_bound来实现从0开始的离散化。
离散化
int t[N]; //t储存了所有需要离散的数据
int a[N]; //a是原始数据
sort(t, t + N);
int size = unique(t, t + N) - t;
for(int i = 0;i < N; ++i)
a[i] = lower_bound(t, t + N, a[i]) - t;
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
const int N = 1000005;
int n;
long long cnt, cntY, many;
long long Y[N << 2];
struct node
{
int type;
long long pos, s, t;
node() {}
node(int _type, long long _pos, long long _s, long long _t) :type(_type), pos(_pos), s(_s), t(_t) {}
bool operator<(const node x) const
{
if (pos == x.pos)
return type < x.type;
else
return pos < x.pos;
}
}e[N << 2];
namespace BIT
{
long long tree[N << 2];
inline int lb(int x) { return x & (~x + 1); }
inline long long sum(int x)
{
long long tot = 0;
for (int i = x; i; i -= lb(i)) tot += tree[i];
return tot;
}
inline void add(int x, long long v)
{
for (int i = x; i <= 4 * many; i += lb(i)) tree[i] += v;
}
}
inline long long max(long long x, long long y) { return x > y ? x : y; }
inline long long min(long long x, long long y) { return x > y ? y : x; }
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
cnt = 0;
cntY = 0;
memset(BIT::tree, 0, sizeof(BIT::tree));
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (y1 == y2)//横
{
if (x1 > x2) std::swap(x1, x2);
e[++cnt] = node(0, x1, y1, 1);
e[++cnt] = node(0, x2 + 1, y2, -1);
}
else
e[++cnt] = node(1, x1, min(y1, y2), max(y1, y2));
Y[++cntY] = y1;
Y[++cntY] = y2;
}
std::sort(Y + 1, Y + 1 + cntY);
many = std::unique(Y + 1, Y + 1 + cntY) - Y - 1;
for (int i = 1; i <= cnt; ++i)
{
if (e[i].type == 0)
e[i].s = std::lower_bound(Y + 1, Y + 1 + many, e[i].s) - Y + 1;
else
{
e[i].s = std::lower_bound(Y + 1, Y + 1 + many, e[i].s) - Y + 1;
e[i].t = std::lower_bound(Y + 1, Y + 1 + many, e[i].t) - Y + 1;
}
}
std::sort(e + 1, e + 1 + cnt);
long long ans = 0;
for (int i = 1; i <= cnt; ++i)
{
if (e[i].type == 0)
BIT::add(e[i].s, e[i].t);
else
ans += BIT::sum(e[i].t) - BIT::sum(e[i].s - 1);
}
printf("%lld\n", ans);
}
return 0;
}
注意
代码中的node结构体 当type = 0的时候存的是横线的两个点，pos记录了点的横坐标，s记录了点的纵坐标，t要么是1要么是-1 表示是线段的起点还是终点； 当type = 1的时候存的是竖着的线段，pos记录了线段的横坐标，s和t记录了线段下上两端点的纵坐标，s < t
网友评论