C1. Power Transmission (Easy Edition)[手把手教截距式]

C1. Power Transmission (Easy Edition)[手把手教截距式]

easy版本其实就是计算直线的解析式…

但我这个计算几何渣渣还是不咋会

暴 力 枚 举 两 点 计 算 解 析 式 暴力枚举两点计算解析式 暴力枚举两点计算解析式

这 条 直 线 可 以 和 之 前 的 所 有 斜 率 不 同 的 直 线 相 交 这条直线可以和之前的所有斜率不同的直线相交 这条直线可以和之前的所有斜率不同的直线相交

但这里考虑一个问题,斜率相同但截距不同的也是不同的直线,也要存下来

用 m a p 存 , 键 存 斜 率 , 值 存 斜 率 对 应 的 所 有 截 距 用map存,键存斜率,值存斜率对应的所有截距 用map存,键存斜率,值存斜率对应的所有截距

下 面 推 一 下 小 学 数 学 , 其 中 c 表 示 任 意 常 数 , 所 以 正 负 号 不 重 要 下面推一下小学数学,其中c表示任意常数,所以正负号不重要 下面推一下小学数学,其中c表示任意常数,所以正负号不重要

因 为 A x + B y + c = 0 可 得 y = − A B x + c 因为Ax+By+c=0可得y=frac{-A}{B}x+c 因为Ax+By+c=0可得y=B−A​x+c

y = k x + c , k = − A B y=kx+c,k=frac{-A}{B} y=kx+c,k=B−A​

又 因 为 已 知 两 点 求 k = y 2 − y 1 x 2 − x 1 又因为已知两点求k=frac{y2-y1}{x2-x1} 又因为已知两点求k=x2−x1y2−y1​

得 A = − ( y 2 − y 1 ) , B = ( x 2 − x 1 ) , C = − A x − B y 得A=-(y2-y1),B=(x2-x1),C=-Ax-By 得A=−(y2−y1),B=(x2−x1),C=−Ax−By

这里对应代码中的

int q=x-x2,w=y-y2;
if( q&&w )
{int s=gcd(q,w);A=w/s,B=q/s;if( A<0 )	A=-A,B=-B;//让直线符号统一
}
else if( w==0&&q )	A=0,B=1;//w是0,斜率为0,表达式是和x平行的线,y=()
else if( w&&q==0 )	A=1,B=0;//q是0,斜率不存在,表达式是和y轴平行的线,x=()
A=-A;//A应该是负,见上面的分析
C=-A*x-B*y;

#include <bits/stdc++.h>
using namespace std;
const int maxn=1009;
int X[maxn],Y[maxn],tot,ans,n;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);
}
map< pair<int,int>,set<int> >mp;
int main()
{cin >> n;for(int i=1;i<=n;i++)	cin >> X[i] >> Y[i];for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){int x=X[i],y=Y[i],A,B,C;int x2=X[j],y2=Y[j];int q=x-x2,w=y-y2;if( q&&w ){int s=gcd(q,w);A=w/s,B=q/s;//斜率是y/x, if( A<0 )	A=-A,B=-B;}else if( w==0&&q )	A=0,B=1;else if( w&&q==0 )	A=1,B=0;A=-A;C=-A*x-B*y;pair<int,int> sp(A,B);if( !mp[sp].count(C) ){tot++;mp[sp].insert(C);ans+=(tot-mp[sp].size() );//新加入的直线和所有斜率不同的直线相交 }}cout << ans;
}