题目描述

https://www.acwing.com/problem/content/2876/

算法1

(找规律) $O(n)$

C++ 代码

#include <iostream>
#include <set>
/*
1. 是重边必然不会增加区域数
2. 不是重边一定会增加一个区域数
3. 和其他边每有一个交点就会增加一个区域数 
*/
using namespace std;

typedef pair<double, double> PDD;
set<PDD> line; // 存储直线斜率和偏移量
int res = 1; // 这里注意要从1开始 

void compute(double x, double y)
{
    set<PDD> points; // 存储相交的结点
    PDD iter;

    for(set<PDD>::iterator l = line.begin(); l != line.end(); l ++)
    {
        double a = l->first, b = l->second;
        if(a != x) // 斜率不等不平行
        {
            iter.first = (b - y) / (x - a); // 求公共点
            iter.second = iter.first * x + y;
            points.insert(iter);
        } 
    }   
    res += points.size();
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        double x, y;
        cin >> x >> y;
        int m = line.size();
        line.insert(make_pair(x, y)); 
        if(m != line.size()) // 由于set不会存储重复元素，所以如果有重边必然不会增加 
        {
            res ++;
            compute(x, y);
        }
    }
    cout << res << endl;
    return 0;
}