搭建个网站需要多少钱,做购物网站小图标,品牌设计公司宣传画册,动力 网站建设正题
题目链接:https://codeforces.com/contest/536/problem/C 题目大意 nnn个人#xff0c;第iii个人的游泳速度sis_isi#xff0c;跑步速度是rir_iri。如果跑道长度是RRR#xff0c;泳道长度是SSS那么一个人的用时就是RriSsi\frac{R}{r_i}\frac{S}{s_i}riRsiS…正题
题目链接:https://codeforces.com/contest/536/problem/C 题目大意
nnn个人第iii个人的游泳速度sis_isi跑步速度是rir_iri。如果跑道长度是RRR泳道长度是SSS那么一个人的用时就是RriSsi\frac{R}{r_i}\frac{S}{s_i}riRsiS在R/SR/SR/S不定的情况下然后求出所有可能是用时最短的人。
1≤n≤105,1≤si,ri≤1041\leq n\leq 10^5,1\leq s_i,r_i\leq 10^41≤n≤105,1≤si,ri≤104 解题思路
设kRSk\frac{R}{S}kSR那么用时可以化为kri1si\frac{k}{r_i}\frac{1}{s_i}riksi1。
然后对于一个点(−1ri,1si)(-\frac{1}{r_i},\frac{1}{s_i})(−ri1,si1)我们可以视为用一条斜率为kkk的斜线去截这些点然后让截距最小。
直接维护一个凸壳就好了然后注意因为R/SR/SR/S都是正数所以kkk也得是正数所以要把后段丢掉。
时间复杂度O(nlogn)O(n\log n)O(nlogn)
当然还有一个更神奇的做法因为对于一个sis_isi我们只需要最大的rir_iri所以有用的点数不超过10410^4104可以直接平方暴算。 code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510;
const double eps1e-8;
struct node{double x,y;int id;
}q[N];
int n,top,s[N],ans[N],l[N];
bool cmp(node x,node y)
{return (x.xy.x)?(x.yy.y):(x.xy.x);}
double slope(node a,node b)
{return (b.y-a.y)/(b.x-a.x);}
int main()
{scanf(%d,n);for(int i1;in;i){double x,y;q[i].idi;scanf(%lf%lf,x,y);q[i].x1e5/x;q[i].y1e5/y;}sort(q1,q1n,cmp);for(int i1;in;i)if(q[i].xq[i-1].xq[i].yq[i-1].y)l[i]l[i-1];else l[i]i;for(int i1;in;i){if(q[i].xq[i1].x)continue;while(top1slope(q[s[top-1]],q[s[top]])-epsslope(q[s[top-1]],q[i]))top--;s[top]i;}for(int i1;itop;i){for(int jl[s[i]];js[i];j)ans[q[j].id]1;if(q[s[i]].yq[s[i1]].y)break;}for(int i1;in;i)if(ans[i])printf(%d ,i);return 0;
}
