[数据结构与算法]【题解】洛谷P7778 Dancing Line

前往：我自己搭建的博客

题目

洛谷P7778 Dancing Line

题解

此题关键在于找出点的顺序。观察样例的图像可知：如果路径不平行于坐标轴，那么沿着路径顺序的各点的横坐标和纵坐标至少有一个是单调的；如果路径平行于坐标轴，那么两个坐标都不严格单调。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x7fffffff;
const int maxn=1e6+5;
const ll MOD=998244353;
struct point{ll x,y;}p[maxn];

inline bool cmpx(const point &a,const point &b)
{
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

inline bool cmpx2(const point &a,const point &b)
{
	if(a.x==b.x) return a.y>b.y;
	return a.x<b.x;
}

inline bool cmpy(const point &a,const point &b)
{
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}

inline bool cmpy2(const point &a,const point &b)
{
	if(a.y==b.y) return a.x>b.x;
	return a.y<b.y;
}

inline bool is_vertical(point a,point b,point c)	//判断三个点是否构成直角 
{
	return (a.x-b.x)*(b.x-c.x)+(a.y-b.y)*(b.y-c.y)==0;
}

inline ll dis2(point a,point b)
{
	return ((a.x-b.x)*(a.x-b.x)%MOD+(a.y-b.y)*(a.y-b.y)%MOD)%MOD;
}

inline ll quick(ll a,ll b)
{
	ll ans=1;
	for( ;b;b>>=1)
	{
		if(b&1) ans=ans*a%MOD;
		a=a*a%MOD;
	}
	return ans;
}

int main()
{
	int n; ll v;
	scanf("%d%lld",&n,&v);
	v=quick(v*v%MOD,MOD-2);
	for(int i=0;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);
	bool ok=1; sort(p,p+n+1,cmpx);
	for(int i=2;i<=n;i++) if(!is_vertical(p[i-2],p[i-1],p[i])) {ok=0; break;}
	if(!ok) 
	{
		ok=1; sort(p,p+n+1,cmpy);
		for(int i=2;i<=n;i++) if(!is_vertical(p[i-2],p[i-1],p[i])) {ok=0; break;}
	}
	if(!ok) 
	{
		ok=1; sort(p,p+n+1,cmpx2);
		for(int i=2;i<=n;i++) if(!is_vertical(p[i-2],p[i-1],p[i])) {ok=0; break;}
	}
	if(!ok) 
	{
		ok=1; sort(p,p+n+1,cmpy2);
		for(int i=2;i<=n;i++) if(!is_vertical(p[i-2],p[i-1],p[i])) {ok=0; break;}
	}
	ll ans=0;
	for(int i=0;i<n;i++) ans=(ans+dis2(p[i],p[i+1])*v%MOD)%MOD;
	printf("%lld\n",ans);
	
	return 0;
}