Submission #4034738
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-12;
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;
vector<Line> ls;
REP(_, N) {
double x, y, vx, vy;
cin >> x >> y >> vx >> vy;
auto fpp = [=](double t){return (x + t*vx) + (y + t*vy);};
auto fpm = [=](double t){return (x + t*vx) - (y + t*vy);};
auto fmp = [=](double t){return -(x + t*vx) + (y + t*vy);};
auto fmm = [=](double t){return -(x + t*vx) - (y + t*vy);};
Line l1 = fromPP(0, fpp(0), 1, fpp(1));
Line l2 = fromPP(0, fpm(0), 1, fpm(1));
Line l3 = fromPP(0, fmp(0), 1, fmp(1));
Line l4 = fromPP(0, fmm(0), 1, fmm(1));
ls.push_back(l1);
ls.push_back(l2);
ls.push_back(l3);
ls.push_back(l4);
}
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.size() >= 1 ? deq[0].f(t) : 0;
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 |
2564 Byte |
Status |
WA |
Exec Time |
528 ms |
Memory |
13800 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 |
1 ms |
256 KB |
10 |
AC |
2 ms |
256 KB |
11 |
AC |
5 ms |
384 KB |
12 |
AC |
5 ms |
384 KB |
13 |
AC |
13 ms |
640 KB |
14 |
AC |
11 ms |
512 KB |
15 |
AC |
216 ms |
9196 KB |
16 |
AC |
269 ms |
6892 KB |
17 |
WA |
166 ms |
4464 KB |
18 |
AC |
186 ms |
6000 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 |
528 ms |
13800 KB |
7 |
AC |
2 ms |
256 KB |
8 |
AC |
2 ms |
256 KB |
9 |
WA |
1 ms |
256 KB |