C1. Power Transmission (Easy Edition)
思路:
用两个点A（x1,y1）,B（x2,y2）确定一条直线方程a*x-by = c;
解得a = y1-y2, b = x1-x2, c = a*x1-b*y1;用（a,b,c）三个参数确定一条直线，而且k = a/b（如果存在的条件下）。
遍历所有的两个点，得到一条直线，然后每条直线找到所有与它相交的直线（就是斜率不同的直线）。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<set> #include<algorithm> #include<map> #include<cmath> #include<utility> using namespace std; const int maxn = 55; int x[maxn],y[maxn]; map <pair <int,int> , set <int> > mp; int Gcd(int x,int y){ return y?Gcd(y,x%y):x; } int main(void){ int n,tot = 0,ans = 0; scanf("%d",&n);mp.clear(); for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int x1 = x[i],y1 = y[i]; int x2 = x[j],y2 = y[j]; int x = x1-x2,y = y1-y2,A,B; if(x&&y){ int gcd = Gcd(x,y); A = y/gcd;B = x/gcd; if(A<0) A = -A,B = -B; }else if(y==0&&x!=0){ A = 0;B = 1; }else if(y!=0&&x==0){ A = 1;B = 0; }else A = B = 0; int C = A*x1-B*y1; pair <int,int> sp(A,B); //把斜率相同的直线存在一个容器里 if(!mp[sp].count(C)){ tot++; mp[sp].insert(C); //新加入的直线与其他所有斜率和自己不同的直线相交。 ans += (tot-mp[sp].size()); } } } printf("%d\n",ans); return 0; }
