# D - Line Crossing [문제 링크](https://atcoder.jp/contests/abc402/tasks/abc402_d) ## Problem Statement There are $N$ equally spaced points on a circle labeled clockwise as $1, 2, \ldots, N$. There are $M$ distinct **lines**, where the $i$-th line passes through two distinct points $A_i$ and $B_i$ ($1 \le i \le M$). Find the number of pairs $(i, j)$ satisfying: - $1 \le i < j \le M$, and - the $i$-th and $j$-th lines intersect. ## Constraints - $2 \le N \le 10^6$ - $1 \le M \le 3 \times 10^{5}$ - $1 \le A_i < B_i \le N$ ($1 \le i \le M$) - $(A_i, B_i) \ne (A_j, B_j)$ ($i \ne j$) - All input values are integers. ## Input The input is given from Standard Input in the following format: $ N\ M $ $ A_1\ B_1 $ $ A_2\ B_2 $ $ \vdots $ $ A_M\ B_M $ ## Output Print the answer. ## 풀이 #### 관찰해보면 N이 5일때 1/2, 5/3는 평행하여 서로 꼭짓점이 생기지 않습니다. N이 6일때는 1/2, 6/3, 5/4이 서로 평행하여 꼭짓점이 생기지 않습니다. #### 확장해보면 a/b, a-1/b+1, a-2/b+2, ... 는 서로 평행하여 서로 꼭짓점이 생기지 않습니다. 이것을 a를 1로 고정하여 map을 써서 구분해서 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; map<pair<int, int>, int> lineList; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; long long total=0; for(int i=0;i<m;i++) { int a, b; cin >> a >> b; if(a>b) swap(a, b); int move = a-1; a = 1; b = (b+move-1)%n+1; total += i - lineList[{a, b}]++; } cout << total; } ```