题目描述

输入

输出

样例输入

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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #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
            
             =0;j--){ if (f[i]
             
              =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) j--; if (i<=j){ swap(b[i],b[j]); i++; j--; } } if (l
              
             
            
           
          
         
        
       
      
     

启发

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

卡常时去除冗余状态。