这个题啊,真是流弊
我一开始是蒙圈的

然后就猜测一些性质,比如令(x,y)为当前的坐标
那我们会发现这样的性(gui)质(lv) :

首先所有 y 为偶数的三角形是反着的(顶点向下),同理 y 为奇数的三角是正着的

然后,两个三角的相对位置不变,距离则不变

再然后,任何一个三角都可以通过对称移动到(x,1)

最后任何一个(x,1)形式的三角和(1,1)之间的距离是(x-1)·2

根据上面的性质,我们就可以发现,把任何一个三角的横纵坐标做一些处理,使之成为(x,1)的形式,并且此时将起始坐标点转化为(1,1),这样就好求了许多

在此之前,由于可能三角是倒着的,那么我们就将他们正过来

还有可能是起始点的坐标在询问点的下面,我们要将他们交换

而且翻转时会对 ans 产生一定影响,而且要先交换再翻转
至于原因,请(wo)读(lan)者(de)自(qu)行(jie)考(shi)虑(le)(画个图就好了的)


#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 123546
using namespace std;

template < typename T > IL void of(R T &a) {
    R char c=getchar (); R T w=1, p=0;
    while (!isdigit(c)) { if(c=='-') w=-1; c=getchar (); }
    while (isdigit(c)) { p=p*10+c-'0'; c=getchar (); }
    a=w*p;
}

/* -------------------- Peipei -------------------- */

II n,m,k,s,nx,ny;   

int main()
{
    of(n); of(m); of(k); of(s); of(nx); of(ny);
    R II ans=1e9, now=0;
    for(R II i=1,x,y;i<=m;i++) {
        R II xx=nx, yy=ny;
        now=0;
        of(x); of(y);
        if(nx>x) swap(x,nx), swap(y,ny);
        if(!(ny&1)) nx--, ny--, now--;
        if(!(y&1)) x--, y--, now++;

        x-=nx-1; y-=ny-1;
        if(y>x*2-1) now+=y-(x*2-1);
        if(y<1) now+=1-y;
        y=1;
        now+=(x-1)*2;
        ans=min(ans,now);
        nx=xx; ny=yy;
    }
    ans*=k; ans++;

    if(ans>s) ans=-1;
    else ans=s-ans;
    printf("%d\n",ans);
    exit(0);
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

P`eipei

Why Be King When Can Be God.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *