QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191485 | #7527. Doors of the Wardrobe | Days_of_Future_Past# | WA | 1ms | 6036kb | C++14 | 4.0kb | 2023-09-29 23:50:25 | 2023-09-29 23:50:26 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
typedef long long LL;
typedef long double D;
const int N = 100011;
mt19937 gene(233);
struct P {
D x, y;
void scan() {
cin >> x >> y;
}
bool operator < (const P & b) const {
return x < b.x;
}
P operator - (const P & b) const {
return P{x - b.x, y - b.y};
}
P operator + (const P & b) const {
return P{x + b.x, y + b.y};
}
D operator * (const P & b) const {
return x * b.y - y * b.x;
}
D operator % (const P & b) const {
return x * b.x + y * b.y;
}
D sqrlen() const {
return x * x + y * y;
}
D len() const {
return sqrt(sqrlen());
}
P zoom(const D & l) const {
D lambda = l / len();
return P{lambda * x, lambda * y};
}
void print() const {
cout << x << ' ' << y << endl;
}
void rand() {
x = gene();
y = gene();
}
} a[N], d[N];
P operator * (const D & x, const P & b) {
return P{x * b.x, x * b.y};
}
typedef tree<P, null_type, less<P>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set hull[2];
void insert(P x) {
for(int d = 0; d < 2; d++) {
auto itr = hull[d].lower_bound(x);
bool flag = false;
if(itr == hull[d].end()) {
flag = true;
}else if(itr->x == x.x) {
//cout << itr->y << '?' << x.y << endl;
flag = itr->y < x.y;
}else if(itr == hull[d].begin()) {
flag = true;
}else {
P b = *itr;
itr--;
P a = *itr;
//cout << a.x << ' ' << b.x << ' ' << x.x << endl;
P c{x.x, a.y + (b.y - a.y) * (x.x - a.x) / (b.x - a.x)};
flag = x.y > c.y;
}
if(flag) {
hull[d].erase(hull[d].find(x));
auto itr = hull[d].insert(x).fi;
for(;;) {
auto it2 = itr;
it2++;
if(it2 == hull[d].end()) break;
auto it3 = it2;
it3++;
if(it3 == hull[d].end()) break;
if((*it2 - *itr) * (*it3 - *it2) >= 0) {
hull[d].erase(it2);
}else {
break;
}
}
for(;;) {
auto it2 = itr;
if(it2 == hull[d].begin()) break;
it2--;
auto it3 = it2;
if(it3 == hull[d].begin()) break;
it3--;
if((*it2 - *it3) * (*itr - *it2) >= 0) {
hull[d].erase(it2);
}else {
break;
}
}
}
x = -1 * x;
}
/*printf("insert ");
x.print();
for(int d = 0; d < 2; d++) {
printf("[\n");
for(auto p : hull[d]) {
if(d) p = -1 * p;
p.print();
}
printf("---\n");
}*/
}
D len[2];
void solve(P x) {
if(x.y == 0) {
D x1 = hull[0].begin()->x;
D x2 = hull[0].rbegin()->x;
len[0] = min(x1 * x.x, x2 * x.x);
len[1] = max(x1 * x.x, x2 * x.x);
return;
}
for(int d = 0; d < 2; d++) {
P dir = x;
if(dir.y < 0) {
dir = -1 * dir;
}
int le = 0, ri = hull[d].size();
while(le != ri) {
int mid = (le + ri) / 2;
P a = *hull[d].find_by_order(mid);
P b = *hull[d].find_by_order(mid + 1);
if((b - a) % dir > 0) {
le = mid + 1;
}else {
ri = mid;
}
}
if(d == 0) {
len[0] = len[1] = *(hull[d].find_by_order(le)) % x;
}else {
D val = *(hull[d].find_by_order(le)) % x;
len[0] = min(len[0], val);
len[1] = max(len[1], val);
}
x = -1 * x;
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
//n = 100000;
//m = 100000;
for(int i = 0; i < n; i++) {
a[i].scan();
d[i].scan();
//a[i].rand();
//d[i].rand();
d[i] = d[i].zoom(1);
}
for(int i = 0; i < m; i++) {
P x;
x.scan();
//x.rand();
insert(x);
}
D ans = 0;
for(int i = n - 1; i >= 0; i--) {
solve(d[i]);
D x = a[i] % d[i];
len[0] = min(len[0], x);
len[1] = max(len[1], x);
//cout << len[0] << '!' << len[1] << endl;
//a[i].print();
//d[i].print();
//((len[0] - x) * d[i]).print();
ans += len[1] - len[0];
insert(a[i] + (len[0] - x) * d[i]);
insert(a[i] + (len[1] - x) * d[i]);
}
cout << setprecision(20) << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5900kb
input:
3 4 -3 3 0.6 -0.3 4 -1 1 1 1 -4 1 0 -2 3 2 3 2 -2 -0.5 -2
output:
20.275232907551223616
result:
ok answer is 20.2752329075512 (delta 0)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 6036kb
input:
5 3 0.5 0.4 1 1 0.5 0.4 3 4 0.5 0.35 1 1 0.4 0.4 1 0 0.5 0.3 0 1 0.5 0.4 0.6 0.4 0.5 0.5
output:
2.1691454531540598572
result:
wrong answer expected 0.859813275223096, found 2.16914545315406 (delta 0.60362)