用好强大的STL库

以——“煊哥的难题”为例

STL当中为我们提供了非常多的高效容器，利用好的话可以给我们的程序带来极大的便利

Description

煊哥待在家里实在无聊，于是出了一道难题来考考你们。众所周知，两点确定一条直线，现给出\(2n\)个点的坐标，构成了\(n\)条直线。现在煊哥想知道总共有多少对直线\((L_i,L_j)\)，满足\(L_i\)与\(L_j\)至少有一个公共点\((1<=i<j<=n)\)。

Input

单组输入。第一行输入一个整数n，表示有n条直线。\((1<=n<=100000)\) 接着输入\(n\)行，每行输入四个整数\(x_1\),\(y_1\),\(x_2\),\(y_2\)，表示每条直线上两个不同点的坐标\((x_1,y_1)\)，\((x_2,y_2)\)。

Analysis

这个题目的核心就是直线之间位置关系的判断，我们都知道一个直线除了可以使用两点坐标去表示同样也可以利用斜率+截距去表示，而且利用斜率表示会给我们判断平行线段带来极大的便利。

除了平行但不相重合这一种情况外，其他任何情况下两两之间均有一交点，我们这时候就可以利用map去将该斜率与这一斜率直线的个数进行绑定。利用map与数组去进行斜率与斜率种类编号（方便检索）之间进行互相检索。利用multiset去保存相同斜率下截距的情况用来判断是否会存在相等直线的情况。

用好map，set与数组之间的巧妙映射关系我们就可以比较方便的完成这道题

Accepted Code

/*
 * @Author: Gehrychiang
 * @Date: 2020-02-22 13:57:42
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#pragma GCC optimize(flase)
#include <bits/stdc++.h>
using namespace std;
const int inf = 2147483645;
//主要讨论平行情况
//还需要考虑两条直线完全一样
map<double, int> line;       //用来保存每一种直线出现的次数
double k_ser[100005];        //从编号查斜率
map<double, int> ktoser;     //从斜率查编号
multiset<double> ms[100005]; //用来保存每种斜率下的b
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int n, p = 1;
    double in_k;
    double in_b;
    scanf("%d", &n);
    long long ans = 0;
    int x1, y1, x2, y2;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        if (x1 == x2) //斜率不存在
        {
            in_k = inf; //斜率不存在记为inf
            in_b = x1;  //截距就记为x
            //在斜率都不存在的直线里面选x相同的那就是一样的直线
        }
        else
        {
            in_k = ((y2 - y1) * (1.0)) / (x2 - x1);
            in_b = y2 - in_k * x2; //截距
        }
        if (line[in_k] == 0) //没出现过
        {
            ktoser[in_k] = p; //建立直线k与编号的映射
            k_ser[p] = in_k;
            ++p;
        }
        //处理答案ans
        ans += ms[ktoser[in_k]].count(in_b); //加上相同直线的个数
        ans += (i - 1 - line[in_k]);         //加上与之不想平行的直线个数
        ms[ktoser[in_k]].insert(in_b);       //将in_b放入
        line[in_k]++;                        //计数+1
    }
    // 如果放到最后记录相交的个数会TLE(以此铭记)！！！！
    // for (int i = 1; i < p - 1; i++)
    // {
    //     for (int j = i + 1; j < p; j++)
    //     {
    //         //第i种直线与第j种直线相交
    //         ans += (line[k_ser[i]] * line[k_ser[j]]);
    //     }
    // }
    printf("%lld", ans);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}