汕头市队赛 SRM1X T1

木之本樱

背景

“西瓜是可以种在树上的！”——木之本樱

描述

空地上，一排排的西瓜树拔地而起。

魔法世界里，空地是无限大的。所有的树排成了n条直线，每条直线也是向左右两端无限延伸的。

由于自己姓木（之本）小樱忽然想知道，这些直线能够组成多少个汉字“木”。

我们这样定义一个“木”字：从已有的直线中任取4条，并将其中两条截为射线。若两射线端点为同一点，且两直线均过该端点。对其中一条直线而言，两条射线在同一侧，对另一条直线而言两条射线在异侧，则此时组成一个“木”字。认为两个“木”字相同当且仅当其所取的射线及直线均相同。

比如直线组成这样的图像：

答案为8，8个“木”依次为

输入格式

第一行一个整数n，表示直线的数量。

接下来n行，每行4个整数x₁,y₁,x₂,y₂，表示一条过(x₁,y₁),(x₂,y₂)直线。保证两个坐标不相同。

输出格式

一个整数，表示“木”字的数量。

样例输入1

0 0 1 1

0 0 1 2

0 0 1 3

0 0 1 4

样例输出1

样例输入2

0 0 1 1

0 0 1 2

0 0 1 3

0 0 1 4

0 0 1 5

0 1 1 1

样例输出2

数据范围与约定

对于初（10组数据）：1<=n<=50

对于续（10组数据）：1<=n<=200

对于终（5组数据）：1<=n<=800

对于所有数据：0<=|x₁|,|y₁|,|x₂|,|y₂|<= 20000

样例解释

样例1原图为：

可以发现它与题目举例本质相同。

————————————————————————

这道题求出所有的交点记录每个交点的个数

利用一元二次方程可以求出答案QAQ

精度很重要要数据的话私我

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int M=1e3+7,inf=0x3f3f3f3f;
LL ans,sum;
bool pd(double a,double b){return fabs(a-b)<1e-7;}
int n;
double a[M],b[M];
struct node{double x1,y1,x2,y2;}e[M];
int cnt;
struct pos{double x,y;}q[M*M];
bool cmp(pos a,pos b){return !pd(a.x,b.x)?a.x<b.x:a.y<b.y;}
void prepare(int k){
    if(pd(e[k].x1,e[k].x2)){a[k]=b[k]=inf; return ;}
    a[k]=(e[k].y1-e[k].y2)/(e[k].x1-e[k].x2);
    b[k]=e[k].y1-a[k]*e[k].x1;
}
void calc(int k1,int k2,double& x,double& y){
    if(a[k1]==inf&&b[k1]==inf){
        x=e[k1].x1;
        y=a[k2]*x+b[k2];
    }
    else if(a[k2]==inf&&b[k2]==inf){
        x=e[k2].x1;
        y=a[k1]*x+b[k1];
    }
    else{
        x=(b[k2]-b[k1])/(a[k1]-a[k2]);
        y=a[k1]*x+b[k1];
    }
}
int main()
{
    //freopen("sakura.in","r",stdin);
    //freopen("sakura.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf %lf %lf %lf",&e[i].x1,&e[i].y1,&e[i].x2,&e[i].y2);
        prepare(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++)if(!pd(a[i],a[j])){
            double x,y;
            calc(i,j,x,y);
            q[++cnt]=(pos){x,y};    
        }
    }
    sort(q+1,q+1+cnt,cmp);
    sum=1;
    for(int i=2;i<=cnt;i++){
        if(pd(q[i].x,q[i-1].x)&&pd(q[i].y,q[i-1].y)) sum++;
        if(!pd(q[i].x,q[i-1].x)||!pd(q[i].y,q[i-1].y)||i==cnt){
            LL now=(1+sqrt(1+8*sum))/2;
            if(now>=4) ans=ans+now*(now-1)*(now-2)*(now-3)/24*8;
            sum=1;
        }
    }
    printf("%lld
",ans);
    return 0;
}

View Code

当然还有随机化算法在取模意义下表示分数QAQ 就不用担心精度问题辣

不过扩欧比费马小快所以就改了一波扩欧

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int M=2e3+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
const int P1=1e9+7,P2=998244353;
void exgcd(int a,int b,int&x,int&y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int inv(int x,int mod){
    int v1,v2;
    exgcd(x,mod,v1,v2);
    if(v1<0)v1+=mod;
    return v1;
}
struct num{
    int v1;
    void init(int A){
        v1=(A+P1)%P1;
    }
    num operator+(num x){
        return (num){(v1+x.v1)%P1};
    }
    num operator-(num x){
        return (num){(v1-x.v1+P1)%P1};
    }
    num operator-(){
        return (num){(P1-v1)%P1};
    }
    num operator*(num x){
        return (num){(LL)(v1)*x.v1%P1};
    }
    num operator/(num x){
        return (num){(LL)(v1)*inv(x.v1,P1)%P1};
    }
    bool operator==(num x){
        return v1==x.v1;
    }
    bool operator<(num x)const{
        return v1<x.v1;
    }
};
struct node{num x1,x2,y1,y2;}e[M];
int n;
LL tot;
struct Q{num a,b,c;}q[M];
int sum,p;
struct Ans{num x,y;}ans[M*M];
bool cmp(Ans a,Ans b){return a.x==b.x?a.y<b.y:a.x<b.x;}
void prepare(int k){
    q[k].a=e[k].y1-e[k].y2;
    q[k].b=e[k].x2-e[k].x1;
    q[k].c=-q[k].a*e[k].x1-q[k].b*e[k].y1;
//    printf("[%d]",-q[k].a*e[k].x1-q[k].b*e[k].y1==-q[k].a*e[k].x2-q[k].b*e[k].y2);
}
bool flag;
void calc(int k1,int k2,num& x,num& y){
    flag=0;
    num K=q[k1].a*q[k2].b-q[k2].a*q[k1].b;
    if(K==(num){0}){
        flag=1;
        return;
    }
    y=(q[k2].a*q[k1].c-q[k1].a*q[k2].c)/K;
    x=(q[k2].b*q[k1].c-q[k1].b*q[k2].c)/K;
} 
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        e[i].x1.init(read()); e[i].y1.init(read());
        e[i].x2.init(read()); e[i].y2.init(read());
        prepare(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            num x,y;
            calc(i,j,x,y);
            if(!flag)ans[++sum]=(Ans){x,y};
        }
    }
    sort(ans+1,ans+1+sum,cmp);
    p=1;
    for(int i=2;i<=sum;i++){
        if(ans[i].x==ans[i-1].x&&ans[i].y==ans[i-1].y){
            p++;
            if(i==sum){
                 LL now=(1+sqrt(1+8*p))/2;
                 if(now>=4) tot=tot+now*(now-1)*(now-2)*(now-3)/3;
                 break;
            }
        }
        else{
            LL now=(1+sqrt(1+8*p))/2;
            if(now>=4) tot=tot+now*(now-1)*(now-2)*(now-3)/3;
            p=1;
        }
    }
    printf("%lld
",tot/2);
    return 0;
}

View Code