AcWing 2873. 平面切分
原题链接
困难
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N=1e3+5;
typedef pair<int,int>pii;
typedef pair<double,double>pdd;
int n,ans=1;
set<pii>s;
vector<pii>v;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
s.insert(make_pair(a,b));//set去重
}
//存去重后的k,b
for(auto t:s) v.push_back({t.first,t.second});
//枚举每一个直线
for(int i=0;i<v.size();i++){
int k1=v[i].first,b1=v[i].second;
set<pdd>pos;//交点集合
for(int j=i-1;j>=0;j--){
int k2=v[j].first,b2=v[j].second;
if(k1==k2) continue;//平行
double x=1.0*(b2-b1)/(k1-k2);
double y=1.0*k1*x+b1;
pos.insert(make_pair(x,y));
}
ans+=pos.size()+1;//累加求和
}
cout<<ans<<endl;
return 0;
}