题面
http://codeforces.com/problemset/problem/372/E
题解
前置知识
暂且称原题中的\(P_{2i-1}\)为\(P_i\)，\(P_{2i}\)为\(Q_i\)。
先澄清一下题意，我认为有一点原题的表述不够清楚。就是原题求的是点对集合\(((P_1,Q_1),(P_2,Q_2),…,(P_k,Q_k))\)的个数。集合中的所有点对当然是无序的，但是按照我们对“点对”的理解，每个点对中间的两个点应该是有序的。但是经过对此题样例的分析，本题表达的意思中，点对中的两个点也是无序的。即，\(((A,B),(C,D))\)和\(((B,A),(C,D))\)算作一组解。
以原点作为反演中心，1作为反演幂（只是推荐，因为本题给出的坐标的绝对值最大为50，最小为\(\frac{1}{50}\)，所以做一个几何平均可以使得数据范围基本不变）对原图进行反演。
两个过反演中心的圆在反演中心处相切，等价于反演后是两条相互平行的直线。对原图反演后，\(P_{i}P_j // Q_iQ_j，P_iQ_j // Q_iP_j\)。也就等价于说\(P_iP_jQ_iQ_j\)形成平行四边形。根据平行四边形的判定，这等价于\(P_iQ_i\)与\(P_jQ_j\)的中点重合，且\(P_iQ_i\)与\(P_jQ_j\)不共线。
所以，将原图反演后，我们枚举所有的线段，先按线段的中点将它们分大类；然后在各大类中，再按它们的极角再分小类。然后就转化成一个组合计数问题，对于每一大类分别考虑，其中的每一小类要么不选，要么选一条线段，并且选的线段总数\({\geq}2\)，求方案数。过程中，枚举线段时需要防止重复（即澄清题意部分所指的重复）。
这个问题可以使用总量（各”小类所含线段数+1“之积）减去总数0的方案（1）再减去总数1的方案（各”小类的所含线段数“之和）解决。然后对所有的大类求此答案的和即可解决。
时间复杂度\(O(n^2 \log n)\)。（log来自于分类的排序过程）
代码
#include<bits/stdc++.h>
using namespace std;
#define N 1000
#define rg register
#define In inline
#define ll long long
#define eps 1e-9
const ll mod = (ll)1e9 + 7;
In ll read(){
ll s = 0,ww = 1;
char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘){if(ch == ‘-‘)ww = -1;ch = getchar();}
while(‘0‘ <= ch && ch <= ‘9‘){s = 10 * s + ch - ‘0‘;ch = getchar();}
return s * ww;
}
namespace ModCalc{
In void Inc(ll &x,ll y){
x += y;if(x >= mod)x -= mod;
}
In void Dec(ll &x,ll y){
x -= y;if(x < 0)x += mod;
}
In ll Add(ll x,ll y){
Inc(x,y);return x;
}
In ll Sub(ll x,ll y){
Dec(x,y);return x;
}
}
using namespace ModCalc;
In int sgn(double x){
return x < -eps ? -1 : x > eps;
}
struct vec{
double x,y;
vec(){}
vec(double _x,double _y){x = _x,y = _y;}
In friend vec operator + (vec a,vec b){
return vec(a.x + b.x,a.y + b.y);
}
In friend vec operator - (vec a,vec b){
return vec(a.x - b.x,a.y - b.y);
}
In friend vec operator * (vec a,double k){
return vec(a.x * k,a.y * k);
}
In friend vec operator / (vec a,double k){
return vec(a.x / k,a.y / k);
}
In friend double Dot(vec a,vec b){
return a.x * a.x + b.y * b.y;
}
In friend double Cross(vec a,vec b){
return a.x * b.y - a.y * b.x;
}
In friend bool equ(vec a,vec b){
return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
}
}p[N+5];
struct line{
vec m,v;
line(){}
line(vec _m,vec _v){m = _m,v = _v;}
}l[N*N+5];
int ln;
In vec Adjust(vec a){
int k;
if((k = sgn(a.x)) < 0)a.x = -a.x,a.y = -a.y;
else if(k == 0){
if(sgn(a.y) > 0)a.y = -a.y;
}
return a;
}
In bool cmp(line a,line b){
int k;
if((k = sgn(a.m.x-b.m.x)) != 0)return k < 0;
if((k = sgn(a.m.y-b.m.y)) != 0)return k < 0;
return sgn(Cross(a.v,b.v)) == 1;
}
ll ans,n;
ll a[N*N+5],an;
void Count(){
ll cur = 1;
for(rg int i = 1;i <= an;i++)cur = cur * (a[i] + 1) % mod;
Dec(cur,1);
for(rg int i = 1;i <= an;i++)Dec(cur,a[i]);
Inc(ans,cur);
an = 0;
}
int main(){
// freopen("CF372E.in","r",stdin);
// freopen("CF372E.out","w",stdout);
n = read();
for(rg int i = 1;i <= n;i++){
int a = read(),b = read(),c = read(),d = read();
double x = (double)a / b,y = (double)c / d;
double k = 1 / (x * x + y * y);
p[i] = vec(x,y) * k;
}
for(rg int i = 1;i < n;i++){
for(rg int j = i + 1;j <= n;j++){
ln++;
l[ln].m = (p[i] + p[j]) / 2;
l[ln].v = Adjust(p[i] - p[j]);
}
}
sort(l + 1,l + ln + 1,cmp);
for(rg int i = 1;i <= ln;i++){
if(i == 1 || !equ(l[i].m,l[i-1].m)){
if(i != 1)Count();
a[++an] = 1;
}
else if(sgn(Cross(l[i].v,l[i-1].v)) == 0)a[an]++;
else a[++an] = 1;
}
Count();
cout << ans << endl;
return 0;
}