AcWing 平面切分

1、思路怎么想？

（1）定义：

1）所有数据包括斜率和截距，用pair存储，

2）所有直线都是不重合的，所以用set存储，pair类型的set容器，

3）用一个pair去表示一个焦点，第一个参量是横坐标x，第二个参量是纵坐标y，

（2）原理：

初始化res 为 1 ，

在每条直线进来之后，先res++

再加上，新进来的直线，与已经存在的直线的焦点数，即为答案，

（3）注意：

输入的线条可能为重合线条，所以需要判重，

这里很巧妙，因为set容器不能插入重复的线，所以只需记住上一条线数量，再与新插入进来的线的数量，作比较，

2、代码怎么写？

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>using namespace std;typedef pair<double , double>Pdd; 
set<Pdd> line;//存储直线斜率和截距的set容器
Pdd iter;//表示两直线焦点 
int res = 1;void compute(double x ,double y)
{set<Pdd> points;//存储焦点//遍历所有已经输入的边for(set<Pdd>::iterator l = line.begin() ; l != line.end() ; l++){double a = l->first;double b = l->second;if(a != x)//相交必有焦点，焦点可重合，用set来存去重 {iter.first = (b - y) / (x - a);iter.second = iter.first * x - y;points.insert(iter);}	} res += points.size();
}int main()
{int n;scanf("%d", &n);while(n--){double k , b;scanf("%lf%lf", &k , &b);int m = line.size();line.insert(make_pair(k,b));//make_pair()可直接将k,b转化为一个pair if(m != line.size()){res++;compute(k , b);}}printf("%d" , res);return 0;
}

孙少平上井以后，如果是白天，他总会迫不急待地走出矿区，走向如火如霞的山野之中。噢，他现在看起来不像个煤矿工人，倒像个多愁善感的诗人！

                                                                ——《平凡的世界》