自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 22:33:01，当前版本为作者最后更新于2021-08-08 17:44:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到横纵坐标必然有一个单调不减，因此我们枚举是横坐标还是纵坐标不减，然后检查并计算即可。

由于线可能平行于坐标轴，因此我们在按照横纵坐标排序的时候还要枚举一下应当把另一个关键字按照递增还是递减的规则来排序。

感觉不是很好说清楚 qwq，具体看代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>

#define int long long
const int MN=1e6+6;
const int mod=998244353;

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}
 
int ksm(int y,int z,int p){
    y%=p;int ans=1;
    for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;
    return ans%p;
}
 
int inv(int x,int p){return ksm(x,p-2,p)%p;}

struct Node{int x,y;}pnt[MN];

int n,v;

bool cmp1(Node p,Node q){return (p.x==q.x)?(p.y<q.y):(p.x<q.x);}
bool cmp2(Node p,Node q){return (p.x==q.x)?(p.y>q.y):(p.x<q.x);}
bool cmp3(Node p,Node q){return (p.y==q.y)?(p.x<q.x):(p.y<q.y);}
bool cmp4(Node p,Node q){return (p.y==q.y)?(p.x>q.x):(p.y<q.y);}

bool f(int x,int y,int xx,int yy,int xxx,int yyy){return ((xx-x)*(xx-xxx)+(yy-y)*(yy-yyy)==0);}//判断垂直

bool chk(){
    for(int i=2;i<n;i++)if(!f(pnt[i-1].x,pnt[i-1].y,pnt[i].x,pnt[i].y,pnt[i+1].x,pnt[i+1].y))return 0;
    return 1;
}//判断是否符合条件

int dis(int x,int y,int xx,int yy){
    return ((x-xx)*(x-xx)%mod+(y-yy)*(y-yy)%mod)%mod;
}//计算两点距离的平方

int calc(){
    int res=0;
    for(int i=1;i<n;i++)res=(res+dis(pnt[i].x,pnt[i].y,pnt[i+1].x,pnt[i+1].y))%mod;
    return res%mod*inv(v,mod)%mod*inv(v,mod)%mod;
}//计算答案
 
signed main(void){

    cin>>n>>v;
    n++;
    for(int i=1;i<=n;i++)pnt[i].x=read(),pnt[i].y=read();
    sort(pnt+1,pnt+n+1,cmp1);
    if(chk()){cout<<calc()<<endl;return 0;}
    sort(pnt+1,pnt+n+1,cmp2);
    if(chk()){cout<<calc()<<endl;return 0;}
    sort(pnt+1,pnt+n+1,cmp3);
    if(chk()){cout<<calc()<<endl;return 0;}
    sort(pnt+1,pnt+n+1,cmp4);
    if(chk()){cout<<calc()<<endl;return 0;}
 
    return 0;
}