P7778

云浅知处 · 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;
}