传送门
在一个平面宇宙有很多的灵魂在以固定速度游荡，如果两个灵魂相遇会互相恐吓对方，相对应的两个灵魂各自增加一点经验值。每个灵魂经验值初始为零。给定每个灵魂初始的x坐标，y坐标满足y=ax+b。然后给出x方向的速度和y方向的速度。数据保证给定灵魂位置不同。这些位置是灵魂飘荡过程中某一时刻的状态。要我们求出所有灵魂的经验值都不增加时总经验值。
题目给出某一时刻灵魂的位置和灵魂移动的速度。让我们求所有灵魂最后都不再相遇时灵魂的总经验值。所有灵魂移动的轨迹是一条直线，我们理所当然的想到了直线相交。但即便轨迹相交也不一定相遇，因为还有时间的因素。我们可以以时间为变量，当前坐标为常数建立方程：
xi+VxiTx=xj+VxjTxyi+VyiTy=yj+VyjTyTx=x0i−x0jVxj−VxiTy=y0i−y0jVyj−Vyiy=ax+bTx=Ty=>x0i−x0jVxj−Vxi=y0i−y0jVyj−Vyi=ax0i−ax0jVyj−Vyiresult:aVxj−Vyj=aVxi−Vyi x i + V x i T x = x j + V x j T x y i + V y i T y = y j + V y j T y T x = x 0 i − x 0 j V x j − V x i T y = y 0 i − y 0 j V y j − V y i y = a x + b T x = T y => x 0 i − x 0 j V x j − V x i = y 0 i − y 0 j V y j − V y i = a x 0 i − a x 0 j V y j − V y i r e s u l t : a V x j − V y j = a V x i − V y i 通过上面的一系列推断我们知道了两个灵魂是否相遇只和Vx 和Vy、a有关。所以我们只需要求最后一个公式的值如果相等则代表两灵魂相遇。即便公式算出的值相等、也不一定就会相遇。比如速度为0。 或速度相同但因为起点不同。轨迹是两条相互平行的直线。所以我们需要排除这些情况；
/* problem: Codeforces Round #478 (Div. 2) D. Ghosts author: zxz time: memory: disadvantage: */ #include <iostream> #include <stdlib.h> #include <stdio.h> #include <algorithm> #include <map> #include <set> #include <stack> #include <math.h> #include <queue> #include <string> #include <sstream> #include <vector> #include <string.h> #include <list> #include <time.h> using namespace std; const int maxn = 1e5; const int INF = 1e9; void solve() { unsigned long long n, a, b; scanf("%llu %llu %llu", &n, &a, &b); int X0, v1, v2; map<unsigned long long , int> mp; map<pair<int, int>, int> same; long long ans = 0; while(n--){ scanf("%d %d %d", &X0, &v1, &v2); ans += mp[a*v1 - v2] - same[{v1,v2}]; mp[a*v1 - v2] ++; same[{v1,v2}] ++; } cout << ans * 2 << endl; } int main() { #ifndef ONLINE_JUDGE freopen("cin.txt", "r", stdin); //freopen("cout.txt", "w", stdout); int mao = clock(); #endif solve(); #ifndef ONLINE_JUDGE cerr << "Time:" << clock() - mao << "ms" << endl; #endif return 0; }