题目链接:https://codeforces.com/contest/1163/problem/C2

       题意是给了n个坐标,使他们两两任意相连,然后求出他们所有的直线的相交的点数。

       可以想到的思路就是对于两条直线来说只要k不同就一定会有交点,所以可以想到的思路就是求出所有的直线的斜率,然后两两比较就好了,因为C1的数据范围只有50,所以直接这一暴力就可以写,对于多点共线的情况我们只需要保留一条直线就行了。C2的数据范围是1000,用C1的做法肯定是不行的,其实可以想到对于一条直线来说,它的交点的个数就是不在这条直线上的点的个数,按找这个思路,用map+set去模拟这个过程就好了,直接看代码吧。


AC代码:

#include <bits/stdc++.h>
#define ll long long
#define inf 1e9
using namespace std;
typedef pair<double,double> p;
vector<pair<double,double> > v;
unordered_map<double ,set<double> > ma;
int n;

int main()
{
  scanf("%d", &n);
  for(int i=0;i<n;i++){
    double x, y;
    scanf("%lf%lf",&x, &y);
    v.push_back(p(x, y));
  }
  for(int i=0;i<v.size();i++){
    for(int j=i+1;j<v.size();j++){
      double xx, yy;
      if(v[i].first == v[j].first){
        xx = inf;
        yy = v[i].first;
      }
      else{
        xx = ((double)v[i].second - v[j].second) / (v[i].first - v[j].first);
        yy = v[i].second - xx * v[i].first;
      }
      ma[xx].insert(yy);
    }
  }
  ll cnt = 0;
  for(auto p : ma){
    cnt += p.second.size();
  }
  ll ans = 0;
  for(auto p : ma){
    ans += (cnt - p.second.size()) * p.second.size();
  }
  printf("%lld\n", ans / 2);
  return 0;
}