求t直线交点个数

求t直线交点个数

Problem

直角坐标系下，直线截距式y=kx+b，以截距式(k,b)给定n条直线，求t直线交点的数量(两直线交点、三直线交点。。。) t∈[2,n]

Solution

n 1e4， 暴力枚举O(n(n-1)/2) 5e7莽过了，枚举直线交点，判断是否非负，是否整数，对于每个交点的出现次数累加，这里用map记录了。 对于某个交点，组合数C（n,2）为某交点的出现次数，n是对应的直线数量。因此在一开始初始化F[1-1e4]=i*(i-1)/2；二分数组找到下标i，即为经过该交点的直线个数，然后ans[1~n]记录直线个数的出现次数即可

Code

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n;
struct node{int k,b;
}p[10005];
map<pair<int,int>,int>cnt;
map<pair<int,int>,int>::iterator it;
int f[10005];
int ans[100005];
int main() {scanf("%d",&n);f[1]=0;for(int i=2;i<=10000;i++){f[i]=i*(i-1)/2;}for(int i=1;i<=n;i++){scanf("%d%d",&p[i].k,&p[i].b);}for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){if(p[i].k==p[j].k) continue;else{if((p[j].b-p[i].b)%(p[i].k-p[j].k)!=0) continue;int xx=(p[j].b-p[i].b)*1.0/(p[i].k-p[j].k);int yy=p[i].k*xx+p[i].b;if(xx<0||yy<0) continue;cnt[make_pair(xx,yy)]++;}}}for(it=cnt.begin();it!&#d();it++){cout<<it->first.first<<" "<<it->first.second<<":"<<it->second<<endl;int res=(it->second);int pos=lower_bound(f+1,f+10000+1,res)-f;cout<<pos<<endl;ans[pos]++;}for(int i=2;i<=n;i++){printf("%d ",ans[i]);}}