题目描述

输入

输出

样例输入

4 2

1 2 2

2 0 2

3 0 0

4 2 0

样例输出

1 2 1

数据范围

样例解释

圆圈只在出现的时刻有效。即：时刻t_i时鼠标位置恰好在(x_i,y_i)才能得分。

Kaguya所做的工作就是在这些时刻间移动鼠标。

对于样例：选择点击第2、4个圆圈。

时间[0,2]内，鼠标从(0,0)移动到(0,2)，速度为1，并在时刻2得分。

时间[2,4]内，鼠标从(0,2)移动到(2,0)，速度为sqrt(2)，并在时刻4得分。

因此答案为sqrt(2), a=1 b=2 c=1

解法

二分最大速度的取值，有n^2种。

再利用动态规划解决判定性问题。

注意卡常。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#include<stdlib.h>

#include<time.h>

#define ll long long

#define ln(x,y) int(log(x)/log(y))

#define sqr(x) ((x)*(x))

#define random(x) (rand()%x)

using namespace std;

const char* fin="aP2.in";

const char* fout="aP2.out";

const int inf=0x7fffffff;

const int maxn=2007,maxtot=maxn*maxn;

int n,m,i,j,k,tot,l,r,mid,cnt;

struct node{

    int t,x,y;

}a[maxn];

int gcd(int a,int b){

    if (b) return gcd(b,a%b);

    else return a;

}

struct fuck{

    int a,b,c;

    fuck(){

        a=b=c=0;

    }

    double val(){

        if (c==0) return inf;

        return a*sqrt(b)/c;

    }

    bool operator <=(const fuck& b1){

        return (ll)sqr(a)*b*sqr(b1.c)<=(ll)sqr(b1.a)*b1.b*sqr(c);

    }

    bool operator <(const fuck& b1){

        return (ll)sqr(a)*b*sqr(b1.c)<(ll)sqr(b1.a)*b1.b*sqr(c);

    }

    bool operator >(const fuck& b1){

        return (ll)sqr(a)*b*sqr(b1.c)>(ll)sqr(b1.a)*b1.b*sqr(c);

    }

    void operator =(const fuck& b1){

        a=b1.a;

        b=b1.b;

        c=b1.c;

    }

    void print(){

        int i,j,k;

        for (i=2;i<=int(sqrt(b));i++){

            while (b%sqr(i)==0){

                a*=i;

                b/=sqr(i);

            }

        }

        k=gcd(a,c);

        a/=k;

        c/=k;

        printf("%d %d %d",a,b,c);

    }

}b[maxn*maxn];

bool cmp(fuck a,fuck b){

    return a<b;

}

fuck dist(int sx,int sy,int tx,int ty,int t){

    fuck A;

    A.a=1;

    A.b=sqr(sx-tx)+sqr(sy-ty);

    A.c=t;

    return A;

}

fuck dist(int x,int y){

    fuck A;

    A.a=1;

    A.b=sqr(a[x].x-a[y].x)+sqr(a[x].y-a[y].y);

    A.c=abs(a[x].t-a[y].t);

    return A;

}

int f[maxn],g[maxn];

fuck tmd,tmp;

bool judge(fuck ans){

    int i,j,k;

    f[0]=0;

    g[0]=0;

    for (i=1;i<=n;i++){

        f[i]=0;

        for (j=i-1;j>=0;j--){

            if (f[i]<g[j]+1){

                cnt++;

                if (dist(i,j)<=ans){

                    f[i]=max(f[j]+1,f[i]);

                }

            }

        }

        g[i]=max(f[i],g[i-1]);

    }

    return f[n]>=m;

}

void qsort(int l,int r){

    int i=l,j=r,k=l+(r-l)/2;

    fuck mid=b[k];

    while (i<=j){

        while (b[i]<mid) i++;

        while (b[j]>mid) j--;

        if (i<=j){

            swap(b[i],b[j]);

            i++;

            j--;

        }

    }

    if (l<j) qsort(l,j);

    if (i<r) qsort(i,r);

}

int main(){

    srand(time(0));

    scanf("%d%d",&n,&m);

    a[0].t=a[0].x=a[0].y=0;

    for (i=1;i<=n;i++){

        scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);

    }

    b[++tot].a=0;b[tot].b=0;b[tot].c=1;

    for (i=0;i<=n;i++) {

        tmd.a=tmd.b=tmd.c=0;

        for (j=i+1;j<=n;j++) {

            tmp=dist(i,j);

            if (tmd<tmp) continue;

            b[++tot]=tmp;

            tmd=tmp;

        }

    }

    sort(b+1,b+tot+1,cmp);

    l=1;

    r=tot;

    k=0;

    while (l<r){

        k++;

        mid=(l+r)/2;

        if (judge(b[mid])) r=mid;

        else l=mid+1;

    }

    //printf("%d %d\n",cnt,k);

    b[l].print();

    return 0;

}

启发

最值套最值用二分，当数值不能二分时，考虑取值。

卡常时去除冗余状态。