Submission #102493
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;
cin >> x >> y >> u >> v;
tmp.push_back({ u+v, x+y});
tmp.push_back({ u-v, x-y});
tmp.push_back({-u+v,-x+y});
tmp.push_back({-u-v,-x-y});
}
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;
});
vl.push_back({-1e9,-1e-5});
vl.push_back(tmp[0]);
iter(i,1,4*n){
if(abs(tmp[i].first - tmp[i-1].first) > EPS) vl.push_back(tmp[i]);
}
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;
t = px(vl[ti[tail].second],vl[i]);
if(t > ti[tail].first) break;
ti.pop_back();
}
ti.push_back({t,i});
}
rep(i,m){
double t;
cin >> t;
auto it = upper_bound(all(ti),pair<double,int>{t-EPS,-1});
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 |
1630 Byte |
Status |
WA |
Exec Time |
1413 ms |
Memory |
19288 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 |
21 ms |
804 KB |
10 |
AC |
22 ms |
800 KB |
11 |
AC |
30 ms |
860 KB |
12 |
AC |
29 ms |
936 KB |
13 |
AC |
60 ms |
1192 KB |
14 |
AC |
46 ms |
1196 KB |
15 |
WA |
451 ms |
9100 KB |
16 |
WA |
657 ms |
10516 KB |
17 |
AC |
734 ms |
3212 KB |
18 |
AC |
472 ms |
7816 KB |
2 |
AC |
22 ms |
800 KB |
3 |
AC |
22 ms |
764 KB |
4 |
WA |
21 ms |
800 KB |
5 |
AC |
22 ms |
736 KB |
6 |
AC |
1413 ms |
19288 KB |
7 |
AC |
22 ms |
796 KB |
8 |
AC |
22 ms |
808 KB |
9 |
AC |
22 ms |
804 KB |