CF1468F.Full Turn
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are n persons located on a plane. The i-th person is located at the point (xi,yi) and initially looks at the point (ui,vi).
At the same moment of time, all persons will start to rotate clockwise synchronously with the same angular speed. They will rotate until they do one full 360-degree turn.
It is said that persons A and B made eye contact if person A looks in person B's direction at the same moment when person B looks in person A's direction. If there is a person C located between persons A and B, that will not obstruct A and B from making eye contact. A person can make eye contact with more than one person at the same time.
Calculate the number of pairs of persons that will make eye contact at least once during the rotation (including the initial moment).
平面上有 n 个人。第 i 个人位于点 (xi,yi),初始时正朝向点 (ui,vi)。
在同一时刻,所有人将同步以相同的角速度顺时针旋转,直至完成一整圈 360∘ 的旋转。
若在某一时刻,人 A 的视线方向恰好指向人 B,且同时人 B 的视线方向也恰好指向人 A,则称人 A 与人 B 实现了“眼神接触”。若存在另一个人 C 位于 A 与 B 之间,这并不会阻碍 A 与 B 实现眼神接触。一个人可以在同一时刻与多个人实现眼神接触。
请计算在整段旋转过程中(包括初始时刻),至少发生一次眼神接触的无序人对的数量。
输入格式
The first line contains one integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n (1≤n≤105) — the number of persons. The following n lines describe persons, each line containing four space-separated integers xi,yi,ui,vi (∣xi∣,∣yi∣,∣ui∣,∣vi∣≤109; xi=ui or yi=vi), where (xi,yi) are the coordinates of the point where the i-th person is located and (ui, vi) are the coordinates of the point that the i-th person looks at initially. Each person's location is unique in each test case.
The sum of n over all test cases does not exceed 105.
第一行包含一个整数 t(1≤t≤104)—— 测试用例的数量。
每个测试用例的第一行包含一个整数 n(1≤n≤105)—— 人数。接下来的 n 行描述每个人,每行包含四个以空格分隔的整数 xi,yi,ui,vi(∣xi∣,∣yi∣,∣ui∣,∣vi∣≤109;且满足 xi=ui 或 yi=vi),其中 (xi,yi) 是第 i 个人所在位置的坐标,(ui,vi) 是第 i 个人初始朝向的点的坐标。在每个测试用例中,每个人的位置均唯一。
所有测试用例的 n 值之和不超过 105。
输出格式
For each test case, print one integer — the number of pairs of persons who will make eye contact at least once during the rotation, including the initial moment.
对于每个测试用例,输出一个整数——即在旋转过程中(包括初始时刻)至少发生一次眼神接触的人对数量。
输入输出样例
输入#1
3 2 0 0 0 1 1 0 2 0 3 0 0 1 1 1 1 0 0 1 0 2 0 6 0 0 0 1 1 0 1 2 2 0 2 3 3 0 3 -5 4 0 4 -5 5 0 5 -5
输出#1
0 1 9
输入解题思路,AI测评打分。不知道怎么写?