QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686721#9462. Safest Buildingsucup-team059#AC ✓1ms4244kbC++205.2kb2024-10-29 15:19:282024-10-29 15:19:28

Judging History

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

  • [2024-10-29 15:19:28]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4244kb
  • [2024-10-29 15:19:28]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long

#define db long double
constexpr db EPS = 1E-9;
const db PI = acosl(-1);
int sign(db a){ return a < -EPS ? -1 : a > EPS; }
int cmp(db a,db b) {return sign(a - b);}
struct P {
	db x,y;
	P() {}
	P(db _x,db _y) : x(_x),y(_y){}
	P operator+(P p) {return {x + p.x,y + p.y};}
	P operator-(P p) {return {x - p.x,y - p.y};}
	P operator*(db d) {return {x * d,y * d};}
	P operator/(db d) {return {x / d,y / d};}
	
	bool operator < (P p) const{
		int c = cmp(x,p.x);
		if (c) return c == -1;
		return cmp(y , p.y) == -1;
	}

	bool operator == (P o) const{
		return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
	}
	db dot(P p){return x * p.x + y * p.y;}
	// a * b == |a| * |b| * cos<a,b>  ,大于0为锐角小于0为钝角等于0为直角
	db det(P p){return {x * p.y - y * p.x};} 
	// a * b == |a| * |b| * sin<a,b> == - (b * a) ,a逆时针转多少度可以转到b
	// 大于0 b在a的逆时针方向,等于0共线,小于0 b在a的顺时针方向
	void read(){std::cin >> x >> y;}
	void print(){std::cout << x << " " << y  << "\n";}
	db distTo(P p) {return (*this - p).abs();}
	db alpha() {return atan2l(y,x);}
	db abs() {return sqrtl(abs2());}
	db abs2() {return x * x + y * y;}
	P rot90() {return P(-y,x);} // 逆时针旋转90度
	int quad(){return sign(y) == 1 || (sign(y) == 0 && sign(x) == 1);}
	P unit() {return *this / abs();}
	P rot(db an){return {x * cosl(an) - y * sinl(an),x * sinl(an) + y * cosl(an)};}
};
#define cross(p1,p2,p3) ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3)) // 以p1为起点去考虑<p1,p2> <p1,p3> 
// 大于0 p3在p2的逆时针方向,小于0在顺时针,等于0共线

// 两个直线是否相交
bool chkLL(P p1,P p2,P q1,P q2){
	db a1 = cross(q1,q2,p1),a2 = -cross(q1,q2,p2);
	return sign(a1 + a2) != 0;
}
// 求两直线交点
P isLL(P p1,P p2,P q1,P q2){
	db a1 = cross(q1,q2,p1),a2 = -cross(q1,q2,p2);
	return (p1 * a2 + p2 * a1) / (a1 + a2);
}
// 判断区间 [l1,r1] ,[l2,r2] 是否相交
bool intersect(db l1,db r1,db l2,db r2){
	if (l1 > r1) std::swap(l1,r1);if (l2 > r2) std::swap(l2,r2);
	return !(cmp(r1,l2) == -1 || cmp(r2,l1) == -1);
}
// 两线段是否相交
bool isSS(P p1,P p2,P q1,P q2){
	return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) && 
	crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1) * crossOp(q1,q2,p2) <= 0;
}
// 两线段是否严格相交
bool isSS_strict(P p1,P p2,P q1,P q2){
	return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1) * crossOp(q1,q2,p2) < 0;
}
// m 在不在a和b之间
bool isMiddle(db a,db m,db b){
	return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
// 点m 在不在a和b之间
bool isMiddle(P a,P m,P b){
	return isMiddle(a.x,m.x,b.x) && isMiddle(a.y,m.y,b.y);
}
// 点q在线段上
bool onSeg(P p1,P p2, P q){
	return crossOp(p1,p2,q) == 0 && isMiddle(p1,q,p2);
}
// 点q严格在线段上
bool onSeg_strict(P p1,P p2,P q){
	return crossOp(p1,p2,q) == 0 && sign((q - p1).dot(p1 - p2)) * sign((q - p2).dot(p1 - p2));
}
// 求 q 到 p1p2的投影
P proj(P p1,P p2,P q){
	P dir = p2 - p1;
	return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q以直线p1p2为轴的反射
P refect(P p1,P p2,P q){
	return proj(p1,p2,q) * 2 - q;
}
// 求q到线段p1p2的最短距离
db nearest(P p1,P p2,P q){
	if (p1 == p2) return p1.distTo(q);
	P h = proj(p1,p2,q);
	if (isMiddle(p1,h,p2)){
		return q.distTo(h);
	}
	return std::min(p1.distTo(q),p2.distTo(q));
}
// 求线段p1p2 与线段q1q2的距离
db disSS(P p1,P p2,P q1,P q2){
	if(isSS(p1,p2,q2,q2)) return 0;
	return std::min({nearest(p1,p2,q1),nearest(p1,p2,q2),nearest(q1,q2,p1),nearest(q1,q2,p2)});
}
// 极角排序
// sort(p,p + n,[&](P a,P b){
// 	int qa = a.quad,qb = b.quad;
// 	if (qa != qb) return qa < qb;
// 	return sign(a.det(b)) > 0;
// })
struct Circle{
	P o;
	db r;
	Circle(P o_,db r_) : o(o_), r(r_) {}
};
db areaInter(Circle c1, Circle c2){
	db d = c1.o.distTo(c2.o);
	auto &r1 = c1.r, r2 = c2.r;
	if (d >= r1 + r2) return 0;
	if (r1 + d <= r2) return PI * r1 * r1;
	if (r2 + d <= r1) return PI * r2 * r2;
	db ans = 0;
	db ang1 = acosl((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d));
	ans += ang1 * r1 * r1;
	ans -= r1 * sinl(ang1) * r1 * cosl(ang1);
	db ang2 = acosl((r2 * r2 + d * d - r1 * r1) / (2 * r2 * d));
	ans += ang2 * r2 * r2;
	ans -= r2 * sinl(ang2) * r2 * cosl(ang2);
	return ans;
}

void solve(){
	int n, R, r;
	std::cin >> n >> R >> r;

	Circle base(P(0,0), R - r);
	std::vector<P> p(n);
	for (int i = 0;i < n;i++){
		p[i].read();
	}
	std::vector<std::pair<db, int>> t;

	for (int i = 0;i < n;i++){
		Circle cur(p[i], r);
		t.push_back({areaInter(cur, base),i});
	}
	sort(t.begin(), t.end(),std::greater<>());
	std::vector<int> ans;
	for (auto [a, b] : t){
		if (a == t[0].first){
			ans.push_back(b);
		}
	}
	sort(ans.begin(), ans.end());
	std::cout << ans.size() << '\n';
	for (int i = 0;i < ans.size();i++){
		std::cout << ans[i] + 1 << " \n"[i == (int)ans.size() - 1];
	}

}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t;
	std::cin >> t;

	while (t--){
		solve();
	}

	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4244kb

input:

2
3 10 5
3 4
3 5
3 6
3 10 4
-7 -6
4 5
5 4

output:

1
1
2
2 3

result:

ok 5 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 4176kb

input:

100
6 100 50
42 -31
-66 7
13 84
94 13
51 -14
-18 9
12 100 50
-78 56
-56 -64
-22 54
-41 14
-14 55
21 -83
75 21
-51 56
-31 74
-34 79
22 -37
1 -12
14 100 50
15 71
-44 41
-56 78
-48 22
42 -2
-70 28
51 -34
49 -31
-36 67
63 70
34 9
27 -33
36 -93
-52 -19
8 100 14
21 89
67 60
-12 -3
24 -37
-51 14
-30 8
-75 ...

output:

1
6
1
12
1
11
4
3 4 5 6
7
1 4 6 8 9 12 13
1
1
6
2 4 5 7 13 14
7
1 3 4 5 6 7 9
1
11
9
1 2 3 4 5 6 7 8 9
1
29
1
5
1
29
47
1 2 3 4 5 6 7 9 10 11 12 14 17 18 19 21 22 24 25 26 27 28 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 46 47 48 50 51 52 53 54 55 56
2
21 29
20
1 5 6 7 10 13 14 18 21 25 26 30 33 3...

result:

ok 1674 tokens

Extra Test:

score: 0
Extra Test Passed