QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736417 | #2582. 物理实验 | propane | 0 | 1963ms | 7896kb | C++20 | 5.5kb | 2024-11-12 10:54:38 | 2024-11-12 10:54:39 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<set>
#include<iomanip>
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{
LL x, y;
Point operator-(Point t){
return {x - t.x, y - t.y};
}
LL operator^(Point t){
return x * t.y - y * t.x;
}
LL operator*(Point t){
return x * t.x + y * t.y;
}
LL len2(){
return x * x + y * y;
}
};
struct Fraction{
__int128_t x, y;
long double val;
Fraction(LL _x, LL _y){
val = _x / sqrtl(_y);
__int128_t g = abs(gcd(__int128_t(_x) * _x, __int128_t(_y)));
x = __int128_t(_x) * _x / g;
x *= sign(_x);
y = _y / g;
}
bool operator<(const Fraction &t) const {
__int128_t t1 = x / y;
__int128_t t2 = t.x / t.y;
if (t1 != t2) return t1 < t2;
return (x % y) * t.y < y * (t.x % t.y);
}
bool operator==(const Fraction &t) const {
return x == t.x and y == 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;
}
};
long double cur_x;
Point v;
long double project(Point a){
LL dot = a * v;
return dot / sqrtl(v.len2());
}
long double area(long double y){
return abs(v.x * y - v.y * cur_x);
}
struct Segment{
Point a, b;
long double k() const {
LL dx = b.x - a.x;
LL dy = b.y - a.y;
return sqrtl(dx * dx + dy * dy) / (project(b) - project(a));
}
bool operator<(const Segment &t) const {
long double y1 = a.y + (cur_x - a.x) / (b.x - a.x) * (b.y - a.y);
long double y2 = t.a.y + (cur_x - t.a.x) / (t.b.x - t.a.x) * (t.b.y - t.a.y);
return area(y1) < area(y2);
}
};
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(10);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<Segment> seg(n);
for(int i = 0; i < n; i++){
cin >> seg[i].a.x >> seg[i].a.y >> seg[i].b.x >> seg[i].b.y;
}
Point a, b; long double L;
cin >> a.x >> a.y >> b.x >> b.y >> L;
v = b - a;
vector<Fraction> nums;
vector<Event> event;
nums.reserve(2 * n);
event.reserve(2 * n);
for(int i = 0; i < n; i++){
auto &[p1, p2] = seg[i];
vector<Fraction> q;
for(auto p : {p1, p2}){
auto vv = p - a;
LL dot = vv * v;
nums.push_back(Fraction(dot, v.len2()));
q.push_back(nums.back());
}
if (q[1] < q[0]) swap(q[0], q[1]), swap(p1, p2);
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++];
st[((seg[id].a - a) ^ v) > 0].erase(seg[id]);
}
while(j < event.size() and (event[j].t == nums[i] and event[j].type == 1)){
auto [_, id, type] = event[j++];
st[((seg[id].a - a) ^ v) > 0].insert(seg[id]);
}
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 + 1 < nums.size()){
cur += (L - (nums[j].val - nums[i].val)) / len[j] * sum[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)) / len[j - 1] * sum[j - 1];
}
ans = max(ans, cur);
}
cout << ans << '\n';
}
}
详细
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 12ms
memory: 3912kb
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:
648.7436812169 374.0223192036 270.0970128690 18426.9003219508 653.0455806482 246.7697318533 15343.1969045046 817.6373237405 1243.7315426742 620.5391793394 1320.0566275082 15850.0120024217 1136.9253592359 476.8857542508 414.1898278985 850.8402353573 420.3276238079 18940.1157838223 13045.6202569379 14...
result:
wrong answer wrong answer, 1st numbers differ - expected: '939.774677', found: '648.743681', error = '0.309682'
Test #2:
score: 0
Wrong Answer
time: 1745ms
memory: 7848kb
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.0520326528 2597377.3743440544 21929.1220367422 2894.0091758986 14332.0000021314 3301.0077128122 54920.3123286033 59402.3738040585 37718.7808486373 54764.0089593469 41083.2028447694 67041.8384994659 5004.0198508159 87518.1198773907 65877.5460490806 71160.2290951981 109205.4922828927 17134.60030...
result:
wrong answer wrong answer, 1st numbers differ - expected: '23150.536873', found: '23150.052033', error = '0.000021'
Test #3:
score: 0
Wrong Answer
time: 1963ms
memory: 7896kb
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:
13997442.4491123982 17046548.7858703807 30676078.2830813271 7797481.0319371080 24229284.3975380739 13387746.9424728360 11289245.8563040873 73382913.5993977705 44300442.3630925716 57621157.0259574269 16696606.0002884474 18751576.1057519421 92269323.2616159331 22030848.0532682162 78604984.6819502089 2...
result:
wrong answer wrong answer, 1st numbers differ - expected: '13997587.658382', found: '13997442.449112', error = '0.000010'