QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#143261 | #7027. Machining Disc Rotors | Sorting# | TL | 4291ms | 3876kb | C++23 | 4.9kb | 2023-08-21 00:16:29 | 2023-08-21 00:16:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()
typedef long double ld;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
ld dist() const { return sqrt((ld)dist2()); }
// angle to x-axis in interval [-pi, pi]
ld angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(ld a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<ld> P;
bool circleInter(P a,P b,ld r1,ld r2,pair<P, P>* out) {
if (a == b) { assert(r1 != r2); return false; }
P vec = b - a;
ld d2 = vec.dist2(), sum = r1+r2, dif = r1-r2,
p = (d2 + r1*r1 - r2*r2)/(d2*2), h2 = r1*r1 - p*p*d2;
if (sum*sum < d2 || dif*dif > d2) return false;
P mid = a + vec*p, per = vec.perp() * sqrt(fmax(0, h2) / d2);
*out = {mid + per, mid - per};
return true;
}
const int N = 100 + 3;
const ld PI = acos(-1);
int n, r;
Point<ld> centre[N];
ld radius[N];
Point<ld> angle_to_point(ld angle){
return (Point<ld>{r, 0}).rotate(angle);
}
ld get_angle(Point<ld> p){
ld ans = p.angle();
if(ans < 0)
ans += 2 * PI;
if(ans > 2 * PI)
ans -= 2 * PI;
return ans;
}
ld dist_angle(ld a, ld b){
Point<ld> p1 = angle_to_point(a);
Point<ld> p2 = angle_to_point(b);
return (p1 - p2).dist();
}
bool contains(ld a, ld b){
if(a > b)
swap(a, b);
vector<ld> to_check{PI, 3 * PI, -PI, -3*PI};
for(auto x: to_check)
if(a <= x && x <= b)
return true;
return false;
}
ld calc(pair<ld, ld> a, pair<ld, ld> b){
if(contains(a.first - b.first, a.first - b.second))
return 2 * r;
if(contains(a.second - b.first, a.second - b.second))
return 2 * r;
ld ans = 0;
check_max(ans, dist_angle(a.first, b.first));
check_max(ans, dist_angle(a.first, b.second));
check_max(ans, dist_angle(a.second, b.first));
check_max(ans, dist_angle(a.second, b.second));
return ans;
}
void solve(){
cin >> n >> r;
for(int i = 0; i < n; ++i){
int _x, _y, _r;
cin >> _x >> _y >> _r;
radius[i] = _r;
centre[i] = Point<ld>{_x, _y};
}
vector<pair<ld, ld>> angles;
for(int i = 0; i < n; ++i){
pair<Point<ld>, Point<ld>> p;
if(!circleInter(Point<ld>{0, 0}, centre[i], r, radius[i], &p))
continue;
ld a1 = get_angle(p.first);
ld a2 = get_angle(p.second);
if(a1 > a2)
swap(a1, a2);
ld mid = (a1 + a2) / 2;
Point<ld> p_mid = angle_to_point(mid);
if((centre[i] - p_mid).dist() <= radius[i]){
}
else{
swap(a1, a2);
}
angles.push_back({a1, a2});
}
vector<pair<ld, bool>> sweepline;
for(auto [l, r]: angles){
// cout << l << " " << r << " l r" << endl;
sweepline.push_back({r, true});
sweepline.push_back({l, false});
sweepline.push_back({r + 2 * PI, true});
sweepline.push_back({l + 2 * PI, false});
}
sort(all(sweepline));
vector<pair<ld, ld>> v;
ld prev = -1;
for(auto [angle, start]: sweepline){
if(!start && prev != -1){
// cout << prev << " " << angle << " prev angle" << endl;
v.push_back({prev, angle});
}
prev = angle;
}
ld ans = 0;
for(int i = 0; i < v.size(); ++i){
for(int j = 0; j < v.size(); ++j){
check_max(ans, calc(v[i], v[j]));
}
}
cout << fixed << setprecision(12) << ans << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for(int i = 1; i <= t; ++i){
cout << "Case #" << i << ": ";
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3788kb
input:
1 3 10 0 12 10 11 -6 10 -11 -6 10
output:
Case #1: 18.611654895000
result:
ok 1 cases
Test #2:
score: 0
Accepted
time: 4291ms
memory: 3876kb
input:
5000 3 1000 750 500 625 -250 -625 625 -1000 1000 1000 3 8 -6 -4 5 2 5 5 8 -8 8 1 710 426 -568 994 1 10 -8 6 15 14 931 622 -651 207 -930 438 552 931 890 743 -264 -923 671 889 -315 179 15 761 173 -440 883 81 -938 -310 170 -271 981 91 918 -88 47 136 927 26 903 29 61 -162 936 22 917 129 18 32 595 431 11...
output:
Case #1: 1998.628237512163 Case #2: 15.989025900097 Case #3: 1420.000000000000 Case #4: 19.843134832984 Case #5: 1862.000000000000 Case #6: 1190.000000000000 Case #7: 934.000000000000 Case #8: 542.000000000000 Case #9: 1808.000000000000 Case #10: 1472.000000000000 Case #11: 1790.000000000000 Case #1...
result:
ok 5000 cases
Test #3:
score: -100
Time Limit Exceeded
input:
5000 48 527 -419 -335 761 519 85 1 -47 524 3 301 431 2 489 -193 3 -102 516 2 -69 521 2 526 2 3 68 522 3 507 139 1 490 191 1 514 109 2 388 355 2 203 485 2 -127 510 3 42 524 1 323 414 1 11 526 1 -17 526 3 452 269 3 514 -111 3 94 517 1 525 -27 1 347 396 1 480 215 3 275 447 2 150 504 3 226 475 1 465 -24...
output:
Case #1: 1053.694800690881 Case #2: 1269.660021675118 Case #3: 1143.844334818410 Case #4: 1183.562268928594 Case #5: 1304.000000000000 Case #6: 1173.961249922395 Case #7: 1051.608339700100 Case #8: 1027.719369369271 Case #9: 1314.000000000000 Case #10: 1007.717091814115 Case #11: 1219.559786161210 C...