【NOIP2016提高A组模拟9.15】Osu

本文主要是介绍【NOIP2016提高A组模拟9.15】Osu，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

有n个点，每个点有出现的时间ti和位置(xi,yi)，点到一个就得分，问在得K分的情况下的最小鼠标移动速度

Sample Input

4 2
1 2 2
2 0 2
3 0 0
4 2 0

Sample Output

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

Solution

显然速度只能是任意两个点之间的速度中的一个，全部存到数组里，二分答案
如何判断呢？
打个DP，f[i]表示到第I个点的最大得分，判断是否合法 $O(n^2)$ 转移即可。
注意常数

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 2010 
#define db double
#define ll long long
using namespace std;
int n,m=0,p,f[N],g[N];
struct node{int x,y,t;
};
node b[N];
struct note{int x,y,v;
};
note a[N*N];
db sqr(db x){return x*x;}
int mx(int a,int b){return a>b?a:b;}
int pd(ll m)
{fo(i,1,n){f[i]=0;fd(j,i-1,0){if((int)((sqrt(sqr(b[i].x-b[j].x)+sqr(b[i].y-b[j].y))/(b[i].t-b[j].t))*1000.0)<=m) f[i]=mx(f[i],f[j]+1);if(g[j-1]<f[i]) break;}g[i]=mx(g[i-1],f[i]);}return f[n];
}
int mi(int a,int b)
{int c=1;fo(i,1,b) c*=a;return c;
}
int lca(int m,int n)
{int r=m%n;for(;r>0;r=m%n,m=n,n=r);return m;
}
void write(int m)
{int i=a[m].x,j=a[m].y;int z=b[i].t-b[j].t;int y=sqr(b[i].x-b[j].x)+sqr(b[i].y-b[j].y);int p=2;int x=1;while(y>1&&p<=(int)sqrt(y)){int a=0;for(;y%p==0;y/=p) a++;x*=mi(p,a/2);if(a%2==1) y*=p;p++;}int lc=lca(x,z);x/=lc;z/=lc;printf("%d %d %d",x,y,z);
}
void px(int i,int j)
{int l=i,r=j,m=a[(i+j)/2].v;while (i<j){while(a[i].v<m) i++;while(a[j].v>m) j--;if(i<=j){swap(a[i].v,a[j].v);swap(a[i].x,a[j].x);swap(a[i].y,a[j].y);i++;j--;}}if(l<j) px(l,j);if(i<r) px(i,r);
}
int main()
{scanf("%d %d",&n,&p);b[0].t=b[0].x=b[0].y=0;fo(i,1,n){scanf("%d%d%d",&b[i].t,&b[i].x,&b[i].y);fo(j,0,i-1){a[++m].v=(int)((sqrt(sqr(b[i].x-b[j].x)+sqr(b[i].y-b[j].y))/(b[i].t-b[j].t))*1000.0);a[m].x=i;a[m].y=j;}}px(1,m);int l=1,r=m;while(l+1<r){int x0=a[(l+r)/2].v;if (pd(x0)>=p) r=(l+r)/2;else l=(l+r)/2;}write(r);
}