社区讨论
求助,开O2就过了,不开O2会Wa(估计是精度原因)
P5467[PKUSC2018] PKUSC参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo8os27j
- 此快照首次捕获于
- 2023/10/27 22:06 2 年前
- 此快照最后确认于
- 2023/10/27 22:06 2 年前
CPP
/*
|\+++/|
\ | ^ ^ \
-- | # # \
\_| \
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <iomanip>
const int N = 1550;
const double eps = 1e-7, pi = acos(-1);
int n, m;
int sign(double x) {
if (x > eps) return 1;
else if (x < -eps) return -1;
else return 0;
}
int cmp(double a, double b) {
return sign(a - b);
}
struct Vector {
double x, y, theta;
Vector () {}
Vector(double _x, double _y) {
x = _x, y = _y;
}
double len() {
return sqrt(x * x + y * y);
}
bool operator < (Vector a) {
return cmp(theta, a.theta) < 0;
}
friend bool operator == (Vector a, Vector b) {
return cmp(a.x, b.x) == 0 && cmp(a.y, b.y) == 0;
}
Vector operator + (Vector a) {
return Vector(x + a.x, y + a.y);
}
Vector operator - (Vector a) {
return Vector(x - a.x, y - a.y);
}
Vector operator * (double a) {
return Vector(x * a, y * a);
}
Vector operator / (double a) {
return Vector(x / a, y / a);
}
double operator * (Vector a) {
return x * a.y - y * a.x;
}
}p[N];
struct Line {
Vector u, v;
Line () {}
Line (Vector _u, Vector _v) {
u = _u, v = _v;
}
double len() {
return (v - u).len();
}
}l[N];
double cnt = 0;
bool neline(Vector a, Line b) {
// cnt += a.x + a.y + b.u.x + b.v.x + b.u.y + b.v.y;
if (cmp(a.x, std::min(b.u.x, b.v.x)) == -1) return 0;
if (cmp(a.x, std::max(b.u.x, b.v.x)) == 1) return 0;
if (cmp(a.y, std::min(b.u.y, b.v.y)) == -1) return 0;
if (cmp(a.y, std::max(b.u.y, b.v.y)) == 1) return 0;
return 1;
}
bool online(Vector a, Line b) {
// cnt -= a.x + a.y + b.u.x + b.v.x + b.u.y + b.v.y;
return (neline(a, b) && (sign((a - b.u) * (a - b.v)) == 0));
}
Vector inter (Line a, Line b) {
Vector w = a.u - b.u;
double t = ((b.v - b.u) * w) / ((a.v - a.u) * (b.v - b.u));
return a.u + (a.v - a.u) * t;
}
double dis(Vector a, Line b) {
return fabs((b.u - a) * (b.v - a)) / b.len();
}
bool in(Vector x) {
for (int i = 1; i <= m; ++i) {
if (online(x, l[i])) return 0;
}
Line L = Line(x, x + Vector(0.2333, 0.6666));
int cnt = 0;
for (int i = 1; i <= m; ++i) {
Vector y = inter(L, l[i]);
if (sign(y.y - x.y) > 0 && neline(y, l[i])) cnt ^= 1;
}
return cnt;
}
double get(Vector a, Vector b, double r) {
double res = 0;
Vector c = (b - a) / (b - a).len();
c = Vector(c.y, -c.x) * r;
if (in(c)) {
if (a.theta > b.theta) res += 2 * pi;
res += b.theta - a.theta;
}
return res;
}
double solve(double r) {
double ans = 0;
if (sign(r) == 0) {
if (in(Vector(0, 0))) ans += pi * 2;
return ans;
}
std::vector<Vector> t;
for (int i = 1; i <= m; ++i) {
if (cmp(dis(Vector(0, 0), l[i]), r) >= 0) {
continue;
}
Vector c = (l[i].v - l[i].u) / (l[i].v - l[i].u).len();
Line Tl = (Line){Vector(0, 0), Vector(-c.y, c.x)};
Vector T = inter(Tl, l[i]);
double TL = sqrt(r * r - T.x * T.x - T.y * T.y);
c = c * TL;
// std::cerr << T.x << ' ' << T.y << '\n';
if (neline(T + c, l[i])) t.push_back(T + c);
if (neline(T - c, l[i])) t.push_back(T - c);
}
if (t.empty()) {
if (in(Vector(0, r))) ans += 2 * pi;
return ans;
}
for (auto &it : t) {
it.theta = atan2(it.y, it.x);
}
std::sort(t.begin(), t.end());
for (int i = 0; i < t.size(); ++i) {
if (!(t[i] == t[(i + 1) % t.size()])) {
ans += get(t[i], t[(i + 1) % t.size()], r);
}
}
return ans;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
std::ios::sync_with_stdio(0);
std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m;
for (int i = 1; i <= n; ++i) {
std::cin >> p[i].x >> p[i].y;
}
for (int i = 1; i <= m; ++i) {
std::cin >> l[i].u.x >> l[i].u.y;
}
for (int i = 1; i < m; ++i) {
l[i].v = l[i + 1].u;
}
l[m].v = l[1].u;
double ans = 0;
for (int i = 1; i <= n; ++i) {
ans += solve(p[i].len());
}
std::cout << std::fixed << std::setprecision(5) << ans / pi / 2 << '\n';
return 0;
}
就这篇代码
https://www.luogu.com.cn/record/78248804
https://www.luogu.com.cn/record/78248830
回复
共 4 条回复,欢迎继续交流。
正在加载回复...