题目描述
输入
输出
样例输入
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
",cnt,k);
b[l].print();
return 0;
}启发
最值套最值用二分，当数值不能二分时，考虑取值。
卡常时去除冗余状态。