QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31724 | #21645. 是男人就得80分问题 | Qingyu | Compile Error | / | / | C++20 | 4.2kb | 2022-05-11 23:22:43 | 2022-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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 | | ^