$\huge{共线(line)}$

题目描述

平面上有$n$个点$p_1=(x_1,y_1),...,p_n=(x_n,y_n)$，以及一个特殊点$P=(x_0,y_0)$；保证$i\in[1,n],p_i\ne P$。

问有多少$1\le i\ne j\le n$满足$P,p_i,p_j$共线。

输入格式

第一行三个整数$n,x_0,y_0$。

接下来$n$行，第$i$行两个整数$x_i,y_i$。

输出格式

一行，一个整数表示有多少$1\le i\ne j\le n$满足$P,p_i,p_j$共线。

样例

输入

3 0 1
1 3
2 5
3 4

输出

2

数据范围

对于15%的数据，n<=1000； 对于100%的数据，$1\le n\le10^5,∀i\in[0,n],|x_i|,|y_i|\le10^6,∀i\in[1,n],(x_i,y_i)\ne(x_0,y_0)$。

$\tiny{题目真地码了很久帮忙看看罢（悲）}$

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int lx[114514],ly[114514],ln[114514],ll;

signed main() {
//	freopen("line.in","r",stdin);
//	freopen("line.out","w",stdout);
	int n,Px,Py,px,py,pg,ans=0;
	bool yn;
	scanf("%lld%lld%lld",&n,&Px,&Py);
	for(int i=0; i<n; i++) {
		scanf("%lld%lld",&px,&py);
		px-=Px;
		py-=Py;
		pg=__gcd(px,py);
		px/=pg;
		py/=pg;
		if(!px)py=1;
		else if(!py)px=1;
		yn=1;
		for(int j=0; j<ll; j++) {
			if(lx[j]==px&&ly[j]==py) {
				ln[j]++;
				yn=0;
				ans+=ln[j]-1;
				break;
			}
		}
		if(yn) {
			lx[ll]=px;
			ly[ll]=py;
			ln[ll++]=1;
		}
	}
	if(!ans)ans=1;
	printf("%lld",ans<<1);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}