QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31724#21645. 是男人就得80分问题QingyuCompile Error//C++204.2kb2022-05-11 23:22:432022-05-18 04:28:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 04:28:58]
  • 评测
  • [2022-05-11 23:22:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using db = double;
const db eps = 1e-8;
const db pi = acos(-1);

inline db sqr(db x) { return x * x; }

struct pt {
	db x, y;
	pt (db x = 0, db y = 0) : x(x), y(y) {}
	void in() { cin >> x >> y; }
};
using poly = vector<pt>;

pt operator + (const pt &p1, const pt &p2) {
	return pt(p1.x + p2.x, p1.y + p2.y);
}

pt operator - (const pt &p1, const pt &p2) {
	return pt(p1.x - p2.x, p1.y - p2.y);
}

pt operator * (const pt &p, const db &d) {
	return pt(p.x * d, p.y * d);
}

pt operator / (const pt &p, const db &d) {
	return pt(p.x / d, p.y / d);
}

db vect(const pt &p1, const pt &p2) {
	return p1.x * p2.y - p1.y * p2.x;
}

db vect(const pt &p, const pt &p1, const pt &p2) {
	return vect(p1 - p, p2 - p);
}

db scal(const pt &p1, const pt &p2) {
	return p1.x * p2.x + p1.y * p2.y;
}

db getAngle(const pt &p) {
	return atan2(p.y, p.x);
}

db dis(pt p) {
	return sqrt(sqr(p.x) + sqr(p.y));
}

pt rot(pt p, db d) {
	return pt(p.x * cos(d) - p.y * sin(d), p.x * sin(d) + p.y * cos(d));
}

void getEquation(pt p1, pt p2, db &a, db &b) {
	db dx = p2.x - p1.x, dy = p2.y - p1.y;
	assert(fabs(dx) > eps);
	a = dy / dx;
	b = p1.y - a * p1.x;
}

db common(pt p1, pt p2, pt p3, pt p4) {
	int sgn = 1;
	if (fabs(p1.x - p2.x) < eps || fabs(p3.x - p4.x) < eps) return 0;
	if (fabs(p1.x > p2.x)) swap(p1, p2), sgn *= -1;
	if (fabs(p3.x > p4.x)) swap(p3, p4), sgn *= -1;
	db l = max(p1.x, p3.x), r = min(p2.x, p4.x);
	if (r < l + eps) return 0;
	db a1, b1, a2, b2;
	getEquation(p1, p2, a1, b1);
	getEquation(p3, p4, a2, b2);
	db fl1 = a1 * l + b1, fr1 = a1 * r + b1;
	db fl2 = a2 * l + b2, fr2 = a2 * r + b2;
	if (fl1 < fl2 && fr1 < fr2) return sgn * (r - l) * (fl1 + fr1) / 2;
	if (fl2 < fl1 && fr2 < fr1) return sgn * (r - l) * (fl2 + fr2) / 2;
	db x = (b2 - b1) / (a1 - a2);
	db fx = a1 * x + b1;
	return sgn * ((x - l) * (min(fl1, fl2) + fx) / 2 + (r - x) * (min(fr1, fr2) + fx) / 2);
}

bool isCommon(const poly &A, const poly &B) {
	db sum = 0;
	for (int i = 0; i < A.size(); i++) {
		pt p1 = A[i], p2 = A[(i + 1) % A.size()];
		for (int j = 0; j < B.size(); j++) {
			pt p3 = B[j], p4 = B[(j + 1) % B.size()];
			sum += common(p1, p2, p3, p4);
		}
	}
	if (fabs(sum) > eps) return 1;
	return 0;
}

db common(const poly &A, const poly &B) {
	db sum = 0;
	for (int i = 0; i < A.size(); i++) {
		pt p1 = A[i], p2 = A[(i + 1) % A.size()];
		pt norm = (p2 - p1) / dis(p2 - p1);
		db v1 = scal(norm, p1), v2 = scal(norm, p2);
		if (v1 > v2) swap(v1, v2);
		for (int j = 0; j < B.size(); j++) {
			pt p3 = B[j], p4 = B[(j + 1) % B.size()];
			if (fabs(vect(p1, p2, p3)) > eps || fabs(vect(p1, p2, p4)) > eps) continue;
			db v3 = scal(norm, p3), v4 = scal(norm, p4);
			if (v3 > v4) swap(v3, v4);
			db val = min(v4, v2) - max(v1, v3);
			sum += max(val, (db)0);
		}
	}
	return sum;
}
poly A, B;

void polyIn(poly &pol) {
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		pt p; p.in();
		pol.push_back(p);
	}
	reverse(pol.begin(), pol.end());
}

void move(poly &pol, pt p1, pt p2) {
	db ang = getAngle(p2 - p1);
	for (auto &p : pol) {
		p = p - p1;
		p = rot(p, -ang);
	}
}

int main() {
	polyIn(A);
	polyIn(B);
	db ans = 0;
	for (int i = 0; i < A.size(); i++) {
		poly _A = A;
		move(_A, A[i], A[(i + 1) % A.size()]);
		for (int j = 0; j < B.size(); j++) {
			poly _B = B;
			move(_B, B[(j + 1) % B.size()], B[j]);
			vector<db> cand;
			for (int T: {-1, 1}) {
				for (pt p : _A) {
					for (int jj = 0; jj < _B.size(); jj++) {
						pt p1 = _B[jj], p2 = _B[(jj + 1) % _B.size()];
						if (fabs(p1.y - p2.y) < eps) continue;
						if (p1.y > p2.y) swap(p1, p2);
						if (p1.y < p.y + eps && p.y - eps < p2.y) {
							db xx = p1.x + (p2.x - p1.x) / (p2.y - p1.y) * (p.y - p1.y);
							cand.push_back((xx - p.x) * T);
						}
					}
				}
				swap(_A, _B);
			}
			sort(cand.begin(), cand.end());
			cand.erase(unique(cand.begin(), cand.end(), [](db x, db y) { return fabs(x - y) < eps; }), cand.end());
			for (db x : cand) {
				poly __B = _B;
				for (pt &p : __B) p = p + pt(x, 0);
				if (isCommon(_A, __B)) continue;
				ans = max(ans, common(_A, __B));
			}
		}
	}
	printf("%.10lf\n", ans);
}
 

Details

answer.code:170:1: error: extended character   is not valid in an identifier
  170 |  
      | ^
answer.code:170:1: error: ‘ ’ does not name a type
  170 |  
      | ^