Project Euler 630

题目

Crossed lines

Given a set, $L$, of unique lines, let $M(L)$ be the number of lines in the set and let $S(L)$ be the sum over every line of the number of times that line is crossed by another line in the set. For example, two sets of three lines are shown below:

In both cases M(L) is 3 and S(L) is 6: each of the three lines is crossed by two other lines. Note that even if the lines cross at a single point, all of the separate crossings of lines are counted.

Consider points $(T{2k−1}, T{2k})$, for integer $k \ge 1$, generated in the following way:

$\begin{aligned}
S0 &= 290797\
S{n+1} &= {S_n}^2 \bmod 50515093\
T_n &= ( S_n \bmod 2000 ) − 1000
\end{aligned}$

For example, the first three points are: $(527, 144), (−488, 732), (−454, −947)$. Given the first $n$ points generated in this manner, let $L_n$ be the set of unique lines that can be formed by joining each point with every other point, the lines being extended indefinitely in both directions. We can then define $M(L_n)$ and $S(L_n)$ as described above.

For example, $M(L3) = 3$ and $S(L_3) = 6$. Also $M(L{100}) = 4948$ and $S(L_{100}) = 24477690$.

Find $S(L_{2500})$.

解决方案

斜率相同的两条的直线永远不会相交，斜率不相同那么两条直线就会相交。

将每条斜率相同的直线划分汇集到一起，假设为$ki$条。如果一共有$n$组斜率两两不相同的直线，那么$M(L)=\sum{i=1}^nki$，并且$S(L)=\sum{i=1}^n k_i\cdot (M(L)-k_i)$。

实现时，每一条直线都分别用两个点表示，因此引出两个问题：不同斜率的直线如何分类，以及如何对直线进行去重。

为解决第一个问题，我们为这一些直线进行“定向”,即为沿着直线的两个方向指定一个向量。斜率相同的直线，定的方向都相同。然后就将这些直线将它们定下的方向向量作为关键字进行极角排序，排序完成后，相邻两条直线对应向量叉积若为$0$，那么说明它们是同一斜率下的。

为解决第二个问题，考虑两条斜率相同的直线$P_1P_2$和$Q_1Q_2$是否为同一直线，并且已经定向成$\overrightarrow{P_1P_2},\overrightarrow{Q_1Q_2}$。为了方便第二步去重，首先极角排序时就需要内部处理好斜率相同时直线的位置。如果$\overrightarrow{P_1P_2}\times\overrightarrow{P_1Q_1}>0$，那么说明直线$Q_1Q_2$在$P_1P_2$的左（上）边。因此极角排序时，还需要以$\overrightarrow{P_1P_2}\times\overrightarrow{P_1Q_1}$的正负性作为第二关键字进行排序。最终去重时，如果$\overrightarrow{P_1P_2}\times\overrightarrow{P_1Q_1}=0$，那么说明两条直线其实是同一条，并去除。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
typedef long long ll;
const int N=2500;
int S[N*2+4],T[N*2+4];
struct P {
    ll x, y;
    // 向量减法
    P(ll xx=0,ll yy=0):x(xx),y(yy){}
    P operator-(P p) const {
        return {x - p.x, y - p.y};
    }
    // 向量叉积
    ll operator^(P p) const {
        return x * p.y - y * p.x;
    }
    bool operator < (P&p) const{
        return x<p.x||x==p.x&&y<p.y;
    }
}p[N+4];
struct L {
    P p1, p2;
    L(){}
    L(P p1, P p2) {
        this->p1 = p1;
        this->p2 = p2;
    }
    P vec(){return p2-p1;}
    bool operator ==(L &l){
        return ((vec())^(l.vec()))==0&&(vec()^(l.p1-p1))==0;
    }
    bool operator < (L &l){
        ll v=((vec())^(l.vec()));
        if(v!=0) return v<0;
        return (vec()^(l.p1-p1))<0;
    }

}l[N*(N-1)/2+4];
int np=0,nl=0;
int main(){
    S[0]=290797;
    for(int i=1;i<=N*2;i++){
        S[i]=1ll*S[i-1]*S[i-1]%50515093;
        T[i]=S[i]%2000-1000;
    }
    for(int i=2;i<=N+N;i+=2)
        p[++np]=P(T[i-1],T[i]);
    sort(p+1,p+np+1);
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
            l[++nl]=L(p[i],p[j]);
    sort(l+1,l+nl+1);
    nl=unique(l+1,l+nl+1)-l-1;
    ll ans=1ll*nl*(nl-1);
    for(int i=1,j=1;i<=nl;i=j){
        for(;j<=nl&&(l[i].vec()^l[j].vec())==0;++j);
        ans-=1ll*(j-i)*(j-i-1);
    }
    printf("%lld\n",ans);
}