Submission #4034681
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}
struct Line {
double a;
double b;
double f(double x) {
return a * x + b;
}
};
// 2 点 (x1, y1), (x2, y2) を通る直線を返す
Line fromPP(double x1, double y1, double x2, double y2) {
double dx = x2 - x1;
double dy = y2 - y1;
double m = (dy / dx);
return (Line) { m, -m*x1 + y1 };
}
bool check(Line l1, Line l2, Line l3) {
return (l1.a-l2.a)*(l3.b-l2.b) <= (l2.a-l3.a)*(l2.b-l1.b);
}
const double EPS = 1e-9;
bool isZero(double x) {
return abs(x) < EPS;
}
const int MAX_M = 112345;
double ans[MAX_M];
int main2() {
int N, M;
cin >> N >> M;
double constant = 0;
vector<Line> ls;
REP(_, N) {
double x, y, vx, vy;
cin >> x >> y >> vx >> vy;
auto f = [=](double t){
return abs(x + t*vx) + abs(y + t*vy);
};
if (isZero(vx) && isZero(vy)) {
constant = max(constant, (x + y));
} else if (isZero(vx) || isZero(vy)) {
if (isZero(vx)) {
swap(x, y);
swap(vx, vy);
}
// assert(vx != 0 && vy == 0);
double t1 = (double) -x / vx;
Line l1 = fromPP(t1-1, f(t1-1), t1, f(t1));
Line l2 = fromPP(t1, f(t1), t1+1, f(t1+1));
ls.push_back(l1);
ls.push_back(l2);
} else {
double t1 = (double) -x / vx;
double t2 = (double) -y / vy;
if (isZero(t1 - t2)) {
Line l1 = fromPP(t1-1, f(t1-1), t1, f(t1));
Line l2 = fromPP(t1, f(t1), t1+1, f(t1+1));
ls.push_back(l1);
ls.push_back(l2);
} else {
if (t1 > t2) {
swap(t1, t2);
swap(x, y);
swap(vx, vy);
}
Line l1 = fromPP(t1-1, f(t1-1), t1, f(t1));
Line l2 = fromPP(t1, f(t1), t2, f(t2));
Line l3 = fromPP(t2, f(t2), t2+1, f(t2+1));
ls.push_back(l1);
ls.push_back(l2);
ls.push_back(l3);
}
}
}
sort(ALL(ls), [](const Line&a, const Line&b) -> bool {
return a.a < b.a;
});
deque<Line> deq;
for (Line line : ls) {
while (deq.size() >= 2 && check(deq[deq.size()-2], deq[deq.size()-1], line))
deq.pop_back();
deq.push_back(line);
}
vector< pair<double, int> > ts;
REP(i, M) {
double t; cin >> t;
ts.push_back(make_pair(t, i));
}
sort(ALL(ts));
for (auto ti : ts) {
double t = ti.first;
int index = ti.second;
while (deq.size() >= 2 && deq[0].f(t) <= deq[1].f(t)) deq.pop_front();
double val = deq[0].f(t);
val = max(val, constant);
ans[index] = val;
}
REP(i, M)
printf("%.10f\n", ans[i]);
return 0;
}
int main() {
for (;!cin.eof();cin>>ws)
main2();
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Moving Points |
User |
hs484 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3230 Byte |
Status |
WA |
Exec Time |
517 ms |
Memory |
12136 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 |
2 ms |
384 KB |
10 |
AC |
2 ms |
256 KB |
11 |
AC |
5 ms |
384 KB |
12 |
AC |
5 ms |
384 KB |
13 |
AC |
13 ms |
512 KB |
14 |
AC |
11 ms |
512 KB |
15 |
AC |
210 ms |
5872 KB |
16 |
AC |
264 ms |
6764 KB |
17 |
WA |
166 ms |
3696 KB |
18 |
AC |
176 ms |
3824 KB |
2 |
AC |
1 ms |
256 KB |
3 |
AC |
1 ms |
256 KB |
4 |
AC |
1 ms |
256 KB |
5 |
AC |
1 ms |
256 KB |
6 |
AC |
517 ms |
12136 KB |
7 |
AC |
2 ms |
256 KB |
8 |
AC |
2 ms |
256 KB |
9 |
AC |
1 ms |
256 KB |