QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#289376 | #7862. Land Trade | ucup-team180# | TL | 1ms | 4116kb | C++17 | 9.3kb | 2023-12-23 17:21:51 | 2023-12-23 17:21:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct frac{
long long num, den;
frac(){
}
frac(long long num_, long long den_ = 1){
num = num_;
den = den_;
if (den < 0){
num *= -1;
den *= -1;
}
}
bool operator ==(frac x){
return num * x.den == x.num * den;
}
bool operator <(frac x){
return num * x.den < x.num * den;
}
bool operator <=(frac x){
return num * x.den <= x.num * den;
}
frac operator -(frac x){
return frac(num * x.den - x.num * den, den * x.den);
}
double value(){
return (double) num / den;
}
};
struct point{
frac x, y;
point(){
}
point(frac x, frac y): x(x), y(y){
}
bool operator ==(point P){
return x == P.x && y == P.y;
}
bool operator <(point P){
return x < P.x || x == P.x && y < P.y;
}
};
struct line{
long long a, b, c;
line(long long a, long long b, long long c): a(a), b(b), c(c){
}
};
bool is_parallel(line L1, line L2){
return L1.a * L2.b - L1.b * L2.a == 0;
}
point line_intersection(line L1, line L2){
long long det = L1.a * L2.b - L1.b * L2.a;
long long x = (-L1.c) * L2.b - L1.b * (-L2.c);
long long y = L1.a * (-L2.c) - (-L1.c) * L2.a;
return point(frac(x, det), frac(y, det));
}
int main(){
cout << fixed << setprecision(20);
int xmin, xmax, ymin, ymax;
cin >> xmin >> xmax >> ymin >> ymax;
string S;
cin >> S;
int V = 1;
vector<string> T(V);
vector<vector<int>> c(V);
vector<line> L;
L.push_back(line(1, 0, -xmin));
L.push_back(line(-1, 0, xmax));
L.push_back(line(0, 1, -ymin));
L.push_back(line(0, -1, ymax));
int p = 0;
auto add_vertex = [&](){
T.push_back("");
c.push_back(vector<int>(0));
V++;
};
auto number = [&]() -> int {
int ans = 0;
bool neg = false;
if (S[p] == '-'){
neg = true;
p++;
}
while (isdigit(S[p]) != 0){
ans = ans * 10 + (S[p] - '0');
p++;
}
if (neg){
ans *= -1;
}
return ans;
};
auto dfs = [&](auto dfs, int v) -> void {
if (S[p] == '['){
T[v] = "L" + to_string(L.size());
p++;
long long a = number();
p++;
long long b = number();
p++;
long long c = number();
p++;
L.push_back(line(a, b, c));
} else {
p++;
if (S[p] == '!'){
T[v] = "!";
p++;
c[v].push_back(V);
add_vertex();
dfs(dfs, V - 1);
} else {
c[v].push_back(V);
add_vertex();
dfs(dfs, V - 1);
T[v] = S[p];
p++;
c[v].push_back(V);
add_vertex();
dfs(dfs, V - 1);
}
p++;
}
};
dfs(dfs, 0);
int N = L.size();
vector<point> P;
for (int i = 0; i < N; i++){
for (int j = i + 1; j < N; j++){
if (!is_parallel(L[i], L[j])){
point T = line_intersection(L[i], L[j]);
if (frac(xmin) <= T.x && T.x <= frac(xmax) && frac(ymin) <= T.y && T.y <= frac(ymax)){
P.push_back(T);
}
}
}
}
sort(P.begin(), P.end());
P.erase(unique(P.begin(), P.end()), P.end());
int M = P.size();
vector<frac> X;
for (int i = 0; i < M; i++){
X.push_back(P[i].x);
}
X.erase(unique(X.begin(), X.end()), X.end());
int Xcnt = X.size();
vector<int> left(N, Xcnt), right(N, 0);
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
if (!is_parallel(L[i], L[j])){
point T = line_intersection(L[i], L[j]);
if (frac(xmin) <= T.x && T.x <= frac(xmax) && frac(ymin) <= T.y && T.y <= frac(ymax)){
int idx = lower_bound(X.begin(), X.end(), T.x) - X.begin();
left[i] = min(left[i], idx);
right[i] = max(right[i], idx);
}
}
}
}
vector<vector<frac>> Y(Xcnt);
for (int i = 0; i < N; i++){
if (L[i].b != 0){
for (int j = left[i]; j <= right[i]; j++){
Y[j].push_back(frac(-L[i].c * X[j].den - L[i].a * X[j].num, L[i].b * X[j].den));
}
}
}
for (int i = 0; i < Xcnt; i++){
sort(Y[i].begin(), Y[i].end());
Y[i].erase(unique(Y[i].begin(), Y[i].end()), Y[i].end());
}
vector<vector<int>> pos(N, vector<int>(Xcnt, -1));
for (int i = 0; i < N; i++){
if (L[i].b != 0){
for (int j = left[i]; j <= right[i]; j++){
frac y(-L[i].c * X[j].den - L[i].a * X[j].num, L[i].b * X[j].den);
pos[i][j] = lower_bound(Y[j].begin(), Y[j].end(), y) - Y[j].begin();
}
}
}
vector<vector<pair<int, int>>> E(Xcnt - 1);
for (int i = 0; i < N; i++){
if (L[i].b != 0){
for (int j = left[i]; j < right[i]; j++){
E[j].push_back(make_pair(pos[i][j], pos[i][j + 1]));
}
}
}
for (int i = 0; i < Xcnt - 1; i++){
sort(E[i].begin(), E[i].end());
E[i].erase(unique(E[i].begin(), E[i].end()), E[i].end());
}
vector<vector<vector<int>>> idx_E(Xcnt - 1);
for (int i = 0; i < Xcnt - 1; i++){
idx_E[i].resize(E[i].size());
}
for (int i = 0; i < N; i++){
if (L[i].b != 0){
for (int j = left[i]; j < right[i]; j++){
int p = lower_bound(E[j].begin(), E[j].end(), make_pair(pos[i][j], pos[i][j + 1])) - E[j].begin();
idx_E[j][p].push_back(i);
}
}
}
vector<vector<int>> idx_V(Xcnt - 2);
for (int i = 0; i < N; i++){
if (L[i].b == 0){
frac x(-L[i].c, L[i].a);
if (frac(xmin) < x && x < frac(xmax)){
int idx = lower_bound(X.begin(), X.end(), x) - X.begin();
idx_V[idx - 1].push_back(i);
}
}
}
vector<int> sum(Xcnt);
sum[0] = 0;
for (int i = 0; i < Xcnt - 1; i++){
sum[i + 1] = sum[i] + E[i].size() - 1;
}
int V2 = sum[Xcnt - 1];
vector<double> area(V2, 0);
for (int i = 0; i < Xcnt - 1; i++){
for (int j = 0; j < E[i].size() - 1; j++){
double dl = (Y[i][E[i][j + 1].first] - Y[i][E[i][j].first]).value();
double dr = (Y[i + 1][E[i][j + 1].second] - Y[i + 1][E[i][j].second]).value();
double h = (X[i + 1] - X[i]).value();
area[sum[i] + j] = (dl + dr) * h / 2;
}
}
vector<vector<int>> idx_L(Xcnt - 1), idx_R(Xcnt - 1);
for (int i = 0; i < Xcnt - 1; i++){
idx_L[i].resize(Y[i].size() - 1);
idx_R[i].resize(Y[i + 1].size() - 1);
int Ecnt = E[i].size();
for (int j = 0; j < Ecnt - 1; j++){
for (int k = E[i][j].first; k < E[i][j + 1].first; k++){
idx_L[i][k] = sum[i] + j;
}
for (int k = E[i][j].second; k < E[i][j + 1].second; k++){
idx_R[i][k] = sum[i] + j;
}
}
}
vector<vector<pair<int, vector<int>>>> E2(V2);
for (int i = 0; i < Xcnt - 1; i++){
for (int j = 0; j < E[i].size() - 2; j++){
E2[sum[i] + j].push_back(make_pair(sum[i] + j + 1, idx_E[i][j + 1]));
E2[sum[i] + j + 1].push_back(make_pair(sum[i] + j, idx_E[i][j + 1]));
}
}
for (int i = 1; i < Xcnt - 1; i++){
for (int j = 0; j < Y[i].size() - 1; j++){
E2[idx_R[i - 1][j]].push_back(make_pair(idx_L[i][j], idx_V[i - 1]));
E2[idx_L[i][j]].push_back(make_pair(idx_R[i - 1][j], idx_V[i - 1]));
}
}
vector<int> cc(V2, -1);
int cc_cnt = 0;
vector<bool> head(V2, false);
for (int i = 0; i < V2; i++){
if (cc[i] == -1){
cc[i] = cc_cnt;
head[i] = true;
queue<int> Q;
Q.push(i);
while (!Q.empty()){
int v = Q.front();
Q.pop();
for (auto& P : E2[v]){
if (P.second.empty()){
int w = P.first;
if (cc[w] == -1){
cc[w] = cc[v];
Q.push(w);
}
}
}
}
cc_cnt++;
}
}
vector<bool> curr_in(N, false);
for (int i = 0; i < 4; i++){
curr_in[i] = true;
}
for (int i = 4; i < N; i++){
if (L[i].a * xmin + L[i].b * ymin + L[i].c > 0){
curr_in[i] = true;
} else if (L[i].a * xmin + L[i].b * ymin + L[i].c == 0){
if (L[i].a > 0){
curr_in[i] = true;
} else if (L[i].a == 0){
if (L[i].b > 0){
curr_in[i] = true;
}
}
}
}
vector<vector<bool>> cc_in(cc_cnt);
vector<bool> used(V2, false);
auto dfs2 = [&](auto dfs2, int v) -> void {
if (head[v]){
cc_in[cc[v]] = curr_in;
}
for (auto& e : E2[v]){
int w = e.first;
if (!used[w]){
used[w] = true;
for (int idx : e.second){
curr_in[idx] = !curr_in[idx];
}
dfs2(dfs2, w);
for (int idx : e.second){
curr_in[idx] = !curr_in[idx];
}
}
}
};
dfs2(dfs2, 0);
vector<double> area_sum(cc_cnt, 0);
for (int i = 0; i < V2; i++){
area_sum[cc[i]] += area[i];
}
double ans = 0;
for (int i = 0; i < cc_cnt; i++){
auto dfs3 = [&](auto dfs3, int v) -> bool {
if (T[v][0] == 'L'){
return cc_in[i][stoi(T[v].substr(1))];
}
if (T[v] == "!"){
return !dfs3(dfs3, c[v][0]);
}
if (T[v] == "&"){
return dfs3(dfs3, c[v][0]) && dfs3(dfs3, c[v][1]);
}
if (T[v] == "|"){
return dfs3(dfs3, c[v][0]) || dfs3(dfs3, c[v][1]);
}
if (T[v] == "^"){
return dfs3(dfs3, c[v][0]) ^ dfs3(dfs3, c[v][1]);
}
};
if (dfs3(dfs3, 0)){
ans += area_sum[i];
}
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3864kb
input:
0 1 0 1 ([-1,1,0]^[-1,-1,1])
output:
0.50000000000000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
-5 10 -10 5 ((!([1,2,-3]&[10,3,-2]))^([-2,3,1]|[5,-2,7]))
output:
70.45169340463458240720
result:
ok found '70.4516934', expected '70.4516934', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
0 1 -1 1 ([1,1,1]&[-1,-1,-1])
output:
0.00000000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
0 1000 0 1000 (([1,-1,0]&[-1000,999,999])&([1,0,-998]&[0,1,-998]))
output:
0.00050000000000000001
result:
ok found '0.0005000', expected '0.0005000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
-725 165 643 735 ((((!(([22,15,137]|(!([23,-5,-41]^(!([2,25,-515]&[-37,10,487])))))&(!(([25,24,47]^([-24,21,-114]^[19,-7,79]))^[4,20,241]))))^(!((!((!(([30,-1,474]^([14,17,155]^[-31,-6,-153]))|[-15,-15,108]))|(([-26,-11,421]&[-15,-3,-224])&[14,-3,458])))^[9,20,-404])))^(!((!((!(([14,-6,-464]^[-11,8,...
output:
47063.33485244146868353710
result:
ok found '47063.3348524', expected '47063.3348524', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
767 957 738 941 ((!(((!([3,-3,507]^[-30,-10,425]))^[-6,7,643])^((!((!([-11,0,450]^[21,17,-65]))&(!([17,0,64]^[-11,0,804]))))|[-31,10,-687])))&((!(([-34,12,-527]^(!([17,-14,-219]^(!([13,-27,-105]^(!([18,-47,-110]&(!([-9,-20,-455]^[-18,26,-228])))))))))^([-4,0,144]^[10,1,396])))^((!((!([35,0,-221]&[-5...
output:
36999.05865566321881487966
result:
ok found '36999.0586557', expected '36999.0586557', error '0.0000000'
Test #7:
score: -100
Time Limit Exceeded
input:
-513 213 -733 114 (!((!((!((((!([2,16,-57]|[15,40,-272]))^((!(([0,26,315]|[5,-4,-336])^(!([-12,2,218]&([17,-16,-730]&[-7,3,-263])))))^[18,-7,29]))^[5,30,-126])^((!(((!((([8,9,406]^(!([-26,6,63]^[-38,-25,108])))^(([-9,20,220]^(!([-2,-27,213]^[29,16,-269])))|[-12,-4,-586]))^([30,0,-443]|(!((!([-17,0,3...