圆上相交弦

4月11日 · 2018年

圆上相交弦

测试数据下载:

这道题还是要用到红黑树来做

数学上可以证明下面给出的算法是正确的,但是证明从略,只给出操作步骤

首先把每个端点(一共2n个)与原点的夹角求出来

然后按照从小到大排列

之后从0度开始 ,逆时针顺序扫描

如果扫描到的某个点,与它在同一弦上的另一个端点不曾出现在红黑树中,这个端点看作起点,把这个端点的夹角作为key加入到红黑树

如果这个点在同一弦上的另一个端点已经出现在红黑树中,这个点认为是终点,然后看看比对应起点的key更大的key有多少个

其中rank()计算严格小于给定键的键有多少个

size()计算总的键的个数

由于题目保证不可能出现相同的键

所以,比对应起点的key更大的key有多少个,等于size()-rank()-1

加到sum,然后从红黑树删除这个起点和终点

如此循环,直到2n个点全部扫一遍

最后sum就是答案

注意红黑树模板中

key要变成double类型

double key;
int value; // K-V键值对
Node *left, *right; // 左右子树

compareTo的地方做浮点运算,不能直接是int cmp

double cmp = key - (h->key);

非法键值对修改成-999

必要时可以把返回值int改成long long int

下面是一个类,差不多也算是通用类,只是用来记录信息的一个结构体,没有什么成员函数

class Chord {

public:
const double PI = 3.1415926;
int index; // 端点编号
double k; // 倾斜角度

Chord(int index, double x, double y) {
this->index = index;
k = atan2(y, x); // 用arctan计算角度
if (k < 0) k += 2 * PI; // 注意到要统一到0~2pi的范围
}
};
/**
* qsort,按照角度从小到大排序
*/
int comp(const void *pa, const void *pb) {
const double EPS = 10E-8;

// 是对指针排序
Chord *a = *(Chord **) pa;
Chord *b = *(Chord **) pb;

if (fabs(a->k - b->k) < EPS) {
// 首先处理浮点数相等,差值小于epsilon
return 0;
} else {
if (a->k < b->k) {
return -1;
} else {
return 1;
}
}
}
Chord *chords[MAXN * 2] = {0}; // 存放各个端点,之后要排序
double map[MAXN * 2] = {0}; // 便于查找某index的端点的角度是多少
int main() {

RedBlackBST *tree = new RedBlackBST();

int n;
scanf("%d", &n);

// 读入2n个点,存放到数组,并建立index与k的一一对应
// (注:经过测试,这里用map<int,double>可能会引起超时,所以直接用数组来当map)
for (int i = 0; i < n; ++i) {
double x, y;
scanf("%lf%lf", &x, &y);
chords[i * 2] = new Chord(i * 2, x, y);
map[i * 2] = chords[i * 2]->k;
scanf("%lf%lf", &x, &y);
chords[i * 2 + 1] = new Chord(i * 2 + 1, x, y);
map[i * 2 + 1] = chords[i * 2 + 1]->k;

}

// 排序
qsort(chords, n * 2, sizeof(Chord *), comp);

// 开了一个boolean数组来表示某个点在不在红黑树中,这里避免用tree.contains(key)来判断,以加快运行速度
bool isInTree[MAXN * 2] = {false};

long long ans = 0;

for (int i = 0; i < 2 * n; ++i) {
Chord chord = *chords[i];
// 计算对应的起点终点的编号
int otherIndex = chord.index % 2 == 0 ? chord.index + 1 : chord.index - 1;
if (isInTree[otherIndex]) {
// 如果已经出现在红黑树中,计算比它大的有多少个,就是会产生多少交点
double key = map[otherIndex];
ans += tree->size() - tree->rank(key) - 1;
// 然后移除
tree->removeKey(key);
isInTree[otherIndex] = false;
} else {
// 否则加入到红黑树中
isInTree[chord.index] = true;
tree->put(chord.k, 0);
}
}

printf("%lld\n", ans);

}
2 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定
  1. jxtxzzw2018-4-11 · 20:02

    为什么我自己下载数据都要先回复。。。

  2. 闫 壮2018-4-11 · 19:55

    test