本文共 2249 字，大约阅读时间需要 7 分钟。
大概这一题题意:
给你n=2500个点,生成方式给你了
设Ln表示这n个点两两连出来的直线(去重后,例如(1 1) (2 2) (3 3)只有一条直线)
问这些直线之间两两一共有多少个交点
(两条线交在一起算2次,因为A交B一次,B交A一次)
三条线交在一个点算6次,因为AB,AC,BA,BC,CA,CB)
做法:
我们只要考虑平行的,没有交,不平行的都有交,这样就把复杂度弄到n^2级别了
用分数类统计以后直接计算即可
代码(分数类板子比较重要...):
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;int new_s(){ static int s=290797; s=(long long)s*s%50515093; return s;}struct point{ int x; int y; void get() { x=new_s()%2000-1000; y=new_s()%2000-1000; }};int get_sgn(int x){ if (x==0) return 0; if (x>0) return 1; return -1;}struct fenshu{ int fenzi; int fenmu; int sgn() const { return get_sgn(fenzi)*get_sgn(fenmu); } fenshu (int x=0,int y=1) { fenzi=x; fenmu=y; } friend fenshu operator / (const fenshu &a,const fenshu &b) { return fenshu(a.fenzi*b.fenmu,b.fenzi*a.fenmu); } friend fenshu operator * (int k,const fenshu &b) { return fenshu(k*b.fenzi,b.fenmu); } friend fenshu operator * (const fenshu &b,int k) { return fenshu(k*b.fenzi,b.fenmu); } friend fenshu operator - (int y,const fenshu &a) { return fenshu(y*a.fenmu-a.fenzi,a.fenmu); } friend bool operator == (const fenshu &a,const fenshu &b) { if ((a.fenmu==0)^(b.fenmu==0)) return false; return (long long)a.fenzi*b.fenmu==(long long)a.fenmu*b.fenzi; } friend bool operator < (fenshu a,fenshu b) { if (a.fenmu==0) return false; if (b.fenmu==0) return true; int k1=a.sgn(); int k2=b.sgn(); if (k1!=k2) { return k1 (long long)a.fenmu*b.fenzi; } else { return (long long)a.fenzi*b.fenmu<(long long)a.fenmu*b.fenzi; } }};point a[2505];//#define fenshu long doublestruct line{ fenshu k; fenshu b; line () { } line (point a,point bb) { #ifdef fenshu k=(double)(a.y-bb.y)/(a.x-bb.x); #else k=fenshu(a.y-bb.y,a.x-bb.x); #endif if (a.x==bb.x) { #ifdef fenshu k=1e300; b=a.x; #else k=fenshu(1,0); b=fenshu(a.x,1); #endif } else { b=a.y-k*a.x; } } friend bool operator < (const line &a,const line &b) { if ((a.k 1) printf("%d\n",now); ans-=(long long)now*(now-1); now=1; } } ans-=(long long)now*(now-1); cout< <
转载于:https://www.cnblogs.com/absi2011/p/9256604.html