QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#736914 | #2582. 物理实验 | propane | 100 ✓ | 1404ms | 8636kb | C++20 | 6.2kb | 2024-11-12 13:55:26 | 2024-11-12 13:55:27 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<set>
#include<iomanip>
#include<array>
#include<cassert>
using namespace std;
using LL = long long;
template<typename T>
T sign(T x){
if (x > 0) return 1;
if (x < 0) return -1;
return 0;
}
template<typename T>
T abs(T x){
if (x < 0) x = -x;
return x;
}
template<typename T>
T gcd(T a, T b){
if (b == 0) return a;
return gcd(b, a % b);
}
struct Point{
long double x, y;
Point operator+(const Point &t) const {
return {x + t.x, y + t.y};
}
Point operator-(const Point &t) const {
return {x - t.x, y - t.y};
}
Point operator*(long double t) const {
return {x * t, y * t};
}
Point operator/(long double t) const {
return {x / t, y / t};
}
long double operator*(const Point &t) const {
return x * t.x + y * t.y;
}
long double operator^(const Point &t) const {
return x * t.y - y * t.x;
}
long double len(){
return sqrtl(x * x + y * y);
}
};
struct Fraction{
LL x, y; __int128_t v;
long double val;
// _x * _x / y
Fraction(LL _x, LL _y){
val = _x / sqrtl(_y);
__int128_t t = __int128_t(_x) * _x * sign(_x);
v = t / _y;
x = t % _y;
y = _y;
LL g = abs(gcd(x, y));
x /= g; y /= g;
}
bool operator<(const Fraction &t) const {
if (v != t.v) return v < t.v;
return __int128_t(x) * t.y < __int128_t(y) * t.x;
}
bool operator==(const Fraction &t) const {
return v == t.v and x == t.x and y == t.y;
}
};
long double cur_x;
struct Segment{
Point a, b;
long double k() const {
return (b - a).len() / (b.x - a.x);
}
long double y() const {
return a.y + (cur_x - a.x) * (b.y - a.y) / (b.x - a.x);
}
bool operator<(const Segment& t) const {
return abs(y()) < abs(t.y());
}
};
struct Event{
Fraction t; int id, type;
bool operator<(const Event &a) const {
if (t == a.t) return type < a.type;
return t < a.t;
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(15);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<array<LL, 4> > p(n);
for(int i = 0; i < n; i++){
for(auto &x : p[i]){
cin >> x;
}
}
LL x1, y1, x2, y2, L;
cin >> x1 >> y1 >> x2 >> y2 >> L;
LL dx = x2 - x1, dy = y2 - y1;
LL sqr = dx * dx + dy * dy;
Point v1 = {1.0L * dx, 1.0L * dy};
v1 = v1 / v1.len();
Point v2 = v1;
swap(v2.x, v2.y);
v2.x = -v2.x;
vector<Segment> seg(n);
vector<Fraction> nums;
vector<Event> event;
nums.reserve(2 * n);
event.reserve(2 * n);
for(int i = 0; i < n; i++){
auto [x3, y3, x4, y4] = p[i];
vector<Fraction> q;
{
LL dot = (x3 - x1) * dx + (y3 - y1) * dy;
q.push_back(Fraction(dot, sqr));
nums.push_back(q.back());
}
{
LL dot = (x4 - x1) * dx + (y4 - y1) * dy;
q.push_back(Fraction(dot, sqr));
nums.push_back(q.back());
}
if (q[1] < q[0]){
swap(q[0], q[1]);
swap(x3, x4);
swap(y3, y4);
}
Point p1 = {1.0L * x3 - x1, 1.0L * y3 - y1};
Point p2 = {1.0L * x4 - x1, 1.0L * y4 - y1};
seg[i] = {{p1 * v1, p1 * v2}, {p2 * v1, p2 * v2}};
event.push_back({q[0], i, 1});
event.push_back({q[1], i, 0});
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
sort(event.begin(), event.end());
vector<long double> sum(nums.size() - 1);
vector<long double> len(nums.size() - 1);
set<Segment> st[2];
for(int i = 0, j = 0; i + 1 < nums.size(); i++){
len[i] = nums[i + 1].val - nums[i].val;
cur_x = nums[i].val;
while(j < event.size() and (event[j].t == nums[i] and event[j].type == 0)){
auto [_, id, type] = event[j++];
assert(st[seg[id].a.y > 0].erase(seg[id]) == 1);
}
while(j < event.size() and (event[j].t == nums[i] and event[j].type == 1)){
auto [_, id, type] = event[j++];
assert(st[seg[id].a.y > 0].insert(seg[id]).second);
}
for(int k = 0; k < 2; k++){
if (!st[k].empty()){
sum[i] += st[k].begin()->k() * len[i];
}
}
}
long double ans = 0, val = 0;
for(int i = 0, j = 0; i + 1 < nums.size(); i++){
if (i - 1 >= 0){
val -= sum[i - 1];
}
while(j + 1 < nums.size() and nums[j + 1].val - nums[i].val <= L){
val += sum[j++];
}
long double cur = val;
if (nums[j].val - nums[i].val < L and j < sum.size()){
cur += (L - (nums[j].val - nums[i].val)) * (sum[j] / len[j]);
}
ans = max(ans, cur);
}
val = 0;
for(int i = nums.size() - 1, j = nums.size() - 1; i >= 1; i--){
if (i < sum.size()){
val -= sum[i];
}
while(j - 1 >= 0 and nums[i].val - nums[j - 1].val <= L){
val += sum[--j];
}
long double cur = val;
if (nums[i].val - nums[j].val < L and j - 1 >= 0){
cur += (L - (nums[i].val - nums[j].val)) * (sum[j - 1] / len[j - 1]);
}
ans = max(ans, cur);
}
cout << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 40
Accepted
time: 9ms
memory: 3840kb
input:
100 100 7143 -4407 6148 -4332 -3698 1987 -3674 2827 -2240 -6374 -3784 -6054 149 599 327 597 -2580 -4497 -2820 -4347 9219 -1818 6904 502 -5893 1341 -4357 -1890 -3503 -3287 -1087 -1211 -1579 7118 -229 7556 6456 502 1926 -1748 540 6714 -528 6825 1561 8432 -701 8357 422 6998 -41 7462 -1793 3676 1602 517...
output:
939.774677373731881 454.296258128900952 270.097012868959844 17826.678623837209706 693.633849048387312 649.885185246018366 16035.001858504197734 1046.519448570728228 1243.731542674191705 620.682553752388313 1320.056627508153265 19054.040651341545306 1062.022273814217363 684.429560185889714 421.179353...
result:
ok ok, 100 numbers
Test #2:
score: 40
Accepted
time: 1207ms
memory: 8636kb
input:
100 10000 954303 48690 -14339 924721 464270 12166 -1609 433494 873644 42682 -12246 843861 449837 10414 -1919 418980 537496 14550 -6578 506603 552080 15962 -6594 521226 870138 42252 -12332 840332 57161 -702218 -671596 -43163 38907 -433607 -402515 -34409 445719 9913 -1981 414808 399734 5765 -1530 3686...
output:
23150.536873200873069 1591692.183379612658086 21928.604384533717127 2894.660854555706283 14332.000000822500178 10772.200120039927350 61378.575246198913582 113952.276208519384433 34711.411356190636823 54764.078716139272238 76852.122478574662480 87090.617837486461433 5004.104595903303649 79872.5168546...
result:
ok ok, 100 numbers
Test #3:
score: 20
Accepted
time: 1404ms
memory: 8628kb
input:
100 10000 -636684471 -90006000 664665488 86376811 -263230447 -307903883 362658164 -223073366 -575841687 -121133860 614287459 40176834 -258935135 -268238570 347975250 -185982857 -287828480 -521064727 443096738 -422002609 -315452625 -391084040 435133968 -289354496 -560776752 -215271244 624810954 -5458...
output:
13997587.658381920721695 17046702.419933448496522 46390075.522289595246548 7797517.420475882264782 24229463.209407869395363 13387746.942472835994522 11290240.304302504897350 55253758.742534957629687 60559802.179347229281120 80996320.544026866067725 16696606.000288447356979 18751679.499710427773607 7...
result:
ok ok, 100 numbers