过程
T1码了暴力+随机化。
T2没码完。$Kuku$了
T3写了暴力+ puts("86400\n-1"); 骗了点分。
T1
××你告诉我CF E题是T1？？
首先分析问题：求$A,B$使得形如$\frac{A}{x}+\frac{B}{y}=z$的一堆柿子中有一个最小$z$值。
我们都不喜欢这种柿子。
于是进行转换，令$x'=\frac{1}{x},y'=\frac{1}{y}$。
我们都喜欢这样的柿子：
$$Ax'+By'=z$$
因为我们可以用类似斜率优化的思路去维护上/下凸包来解决这个问题。
不过说一点，请不要刚开始就$x=\frac{1}{x}$，一定被卡精度。
可以
- 化柿子，求斜率时用分式。
- 用$\frac100000000{x}$
- 大骂出题人毒瘤
代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 333333
#define LF long double
using namespace std;
template <typename T>
class Mystack{
T A[N*10];
int tp;
public:
Mystack(){tp=0;}
void clear(){tp=0;}
void pop(){tp--;}
T top(){return A[tp-1];}
T ttop(){return A[tp-2];}
void push(const T &k){A[tp++]=k;}
bool empty(){return tp==0;}
int size(){return tp;}
};
struct POINT{
int x,y;
int id,pos;
bool isk;
POINT(){}
POINT(const int a,const int b):x(a),y(b){}
}arr[N];
bool is_d[N],
flg[N],
isc[N];
int pn;
Mystack<POINT>st;
inline bool CMP1(const POINT &a,const POINT &b){
return a.x==b.x?a.y>b.y:a.x>b.x;
}
inline LF xl(POINT a,POINT b){
return (1.0*(a.y-b.y)*a.x*b.x)/(1.0*a.y*b.y*(a.x-b.x));
}
int main(){
// freopen("slay4.in","r",stdin);\
// freopen("1.out","w",stdout);
scanf("%d",&pn);
for(int i=1;i<=pn;i++){
scanf("%d%d",&arr[i].x,&arr[i].y);
arr[i].id=i;
}
sort(arr+1,arr+pn+1,CMP1);
for(int i=1;i<=pn;i++){
arr[i].pos=i;
// cout<<arr[i].x<<" "<<arr[i].y<<endl;
if((arr[i].x<arr[1].x && arr[i].y<arr[1].y) ||
(arr[i].x==arr[1].x && arr[i].y<arr[1].y) ||
(arr[i].x < arr[1].x && arr[i].y==arr[1].y))
arr[i].isk=1;
}
for(int i=1;i<=pn;){
int j=i+1;
while(j<=pn && arr[j].x==arr[i].x && arr[j].y==arr[i].y){is_d[j]=1;j++;}
i=j;
}
st.push(arr[1]);
int t=2;
while(is_d[t] || arr[t].isk)t++;
st.push(arr[t]);
// cout<<t<<endl;
for(int i=t+1;i<=pn;i++){
if(is_d[i] || arr[i].isk || xl(st.top(),arr[i])>=0)
continue;
while(st.size()>1 && xl(st.ttop(),st.top()) > xl(st.top(),arr[i]))
st.pop();
st.push(arr[i]);
}
while(!st.empty()){
isc[st.top().id]=1;
flg[st.top().pos]=1;
st.pop();
//cerr<<123<<endl;
}
for(int i=1;i<=pn;){
if(flg[i]){
int j=i+1;
while(is_d[j]){
isc[arr[j++].id]=1;
}
i=j;
}
else i++;
}
for(int i=1;i<=pn;i++)
if(isc[i])
printf("%d ",i);
puts("");
}
T2T3
gugugu