Codeforces：Dreamplay and Stars

Codeforces：Dreamplay and Stars

题目链接：http://codeforces.com/group/gRkn7bDfsN/contest/212150/problem/C

题目大意：以（ax+by+c=0）形式给出n条线，问能形成多少个三角形。

组合数学

将同一斜率的直线划分为一组，每组的直线数为tot[i].

用num维护前i组的总直线数，num=num+tot[i].

若以两条斜率不同的直线为一对，times维护在前i组中所有直线对数，故times=times+num*tot[i].

ans维护前i组所有直线构造出的三角形数，故ans=ans+times*tot[i].

代码如下：

 1 #include <iostream>
 2 #include <map>
 3 #include <algorithm>
 4 #define mk(x,y) make_pair(x,y)
 5 using namespace std;
 6 typedef pair<int,int> P;
 7 map<P,int>mp;
 8 int tot[300005];
 9 int gcd(int x,int y){
10     return y==0?x:gcd(y,x%y);
11 }
12 int main(void){
13     std::ios::sync_with_stdio(false);
14     int n;
15     cin>>n;
16     for(int i=0;i<n;++i){
17         int x,y,z;
18         cin>>x>>y>>z;
19         if(x==0||y==0)mp[mk(x,y)]++;
20         else{
21             int t=gcd(x,y);
22             mp[mk(x/t,y/t)]++;
23         }
24     }
25     long long ans=0,k=0,num=0,times=0;
26     for(map<P,int>::iterator it=mp.begin();it!=mp.end();++it)
27         tot[k++]=it->second;
28     sort(tot,tot+k);
29     for(int i=0;i<k;++i){
30         if(i>=2)ans+=times*tot[i];
31         times+=num*tot[i];
32         num+=tot[i];
33     }
34     cout<<ans;
35 }