Submission #103081
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,-1e5});
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;
double ans = 0;
auto it = upper_bound(all(ti),pair<double,int>{t-EPS,-1});
//cout << (*it).first << " " << (*it).second << endl;
it--;
printf("%.12f\n",f(vl[(*it).second],t));
}
}
Submission Info
Submission Time |
|
Task |
G - Moving Points |
User |
YellowYell |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
2766 Byte |
Status |
WA |
Exec Time |
1435 ms |
Memory |
15380 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 |
24 ms |
796 KB |
10 |
AC |
23 ms |
796 KB |
11 |
AC |
32 ms |
920 KB |
12 |
AC |
29 ms |
1048 KB |
13 |
AC |
67 ms |
1072 KB |
14 |
AC |
47 ms |
1068 KB |
15 |
WA |
402 ms |
5668 KB |
16 |
WA |
652 ms |
9616 KB |
17 |
AC |
806 ms |
2680 KB |
18 |
AC |
451 ms |
5404 KB |
2 |
AC |
22 ms |
792 KB |
3 |
AC |
22 ms |
800 KB |
4 |
AC |
20 ms |
924 KB |
5 |
AC |
24 ms |
808 KB |
6 |
AC |
1435 ms |
15380 KB |
7 |
AC |
22 ms |
928 KB |
8 |
AC |
24 ms |
928 KB |
9 |
AC |
23 ms |
796 KB |