QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191511#7527. Doors of the WardrobeDays_of_Future_Past#WA 1ms5952kbC++144.0kb2023-09-30 00:14:232023-09-30 00:14:23

Judging History

你现在查看的是最新测评结果

  • [2023-09-30 00:14:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5952kb
  • [2023-09-30 00:14:23]
  • 提交

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;
			if(flag) {
				hull[d].erase(itr);
			}
		}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) {
			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: 5868kb

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: 5952kb

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)