Submission #103079
Source Code Expand
#include <bits/stdc++.h>
#define iter(i,s,n) for(int i=int(s);i<int(n);i++)
#define rep(i,n) iter(i,0,n)
#define all(c) (c).begin(), (c).end()
using namespace std;
typedef pair<double,double> pdd;
const double EPS = 1e-9;
double f(const pdd &l,double t){return l.first*t + l.second;}
double px(const pdd &A,const pdd &B){return (B.second-A.second)/(A.first-B.first);}
int main(){
int n,m;
vector<pair<double,double>> tmp, vl;
cin >> n >> m;
rep(i,n){
double x,y,u,v;
double X,Y,U,V;
cin >> x >> y >> u >> v;
X = abs(x); Y = abs(y); U = abs(u); V = abs(v);
if(U > V){
swap(X,Y); swap(U,V);
swap(x,y); swap(u,v);
}
if(V < EPS) {
tmp.push_back({0.0,X+Y});
} else if (U < EPS){
double ty = -y/v;
tmp.push_back({-V,X+ty*V});
tmp.push_back({+V,X-ty*V});
} else {
double tx = -x/u;
double ty = -y/v;
if(tx > ty){
swap(tx,ty);
swap(X,Y); swap(U,V);
swap(x,y); swap(u,v);
}
tmp.push_back({-U-V,abs(y+tx*v)-tx*(-U-V)});
tmp.push_back({+U-V,abs(y+tx*v)-tx*(+U-V)});
tmp.push_back({+U+V,abs(x+ty*u)-ty*(+U+V)});
}
}
sort(all(tmp),[](const pdd &A, const pdd &B){
if(A.first < B.first) return true;
if(A.first > B.first) return false;
return A.second > B.second;
});
//rep(i,tmp.size()){ cout << tmp[i].first << " " << tmp[i].second << endl; }
vl.push_back({-1e9,-1e-5});
rep(i,tmp.size()){
if(abs(vl[vl.size()-1].first - tmp[i].first) > EPS) vl.push_back(tmp[i]);
}
//puts("-----");
//rep(i,vl.size()) cout << i << " " << vl[i].first << " " << vl[i].second << endl;
//puts("-----");
vector<pair<double,int>> ti;
ti.push_back({-1,0});
for(int i = 1; i < vl.size(); i++){
double t;
while(1){
int tail = ti.size()-1;
//int tail2 = tail-1;
//if(tail2 < 0) break;
t = px(vl[ti[tail].second],vl[i]);
if(t > ti[tail].first) break;
ti.pop_back();
}
ti.push_back({t,i});
}
//puts("-----");
//rep(i,ti.size()) cout << ti[i].first << " " << ti[i].second << endl;
//puts("-----");
rep(i,m){
double t;
cin >> t;
auto it = upper_bound(all(ti),pair<double,int>{t-EPS,-1});
double ans = 0;
ans = max(ans,f(vl[(*it).second],t));
if(it != ti.begin()){
it--;
ans = max(ans,f(vl[(*it).second],t));
it++;
}
if(++it != ti.end()){
ans = max(ans,f(vl[(*it).second],t));
}
//cout << (*it).first << " " << (*it).second << endl;
printf("%.12f\n",ans);
}
}
Submission Info
Submission Time |
|
Task |
G - Moving Points |
User |
YellowYell |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
3009 Byte |
Status |
WA |
Exec Time |
790 ms |
Memory |
13328 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 2, 3, 4, 5, 6, 7, 8, 9 |
Case Name |
Status |
Exec Time |
Memory |
1 |
AC |
22 ms |
936 KB |
10 |
RE |
251 ms |
928 KB |
11 |
AC |
30 ms |
932 KB |
12 |
RE |
251 ms |
884 KB |
13 |
AC |
60 ms |
1176 KB |
14 |
RE |
256 ms |
1064 KB |
15 |
WA |
426 ms |
5632 KB |
16 |
WA |
637 ms |
9612 KB |
17 |
RE |
297 ms |
1188 KB |
18 |
AC |
447 ms |
5388 KB |
2 |
AC |
35 ms |
732 KB |
3 |
AC |
21 ms |
928 KB |
4 |
AC |
21 ms |
924 KB |
5 |
AC |
21 ms |
752 KB |
6 |
RE |
790 ms |
13328 KB |
7 |
AC |
21 ms |
804 KB |
8 |
RE |
246 ms |
808 KB |
9 |
RE |
250 ms |
800 KB |