网友投稿 647 2022-10-18 20:30:11
AcWing 4202. 穿过圆
#include #include #include#include#includeusing namespace std;const int N = 1e3 + 10;typedef pair PII;const double eps = 1e-6;int n, m, k;struct Node { int x, y; int r, cnt;}cir[N], node[N];bitset st[N];bool dist (int a, int b) { double dis1 = node[a].x - cir[b].x; double dis2 = node[a].y - cir[b].y; double dif = sqrt(dis1 * dis1 + dis2 * dis2); return dif <= cir[b].r - eps;}int main () { cin >> n >> m >> k; for (int i = 1; i<= n ;i ++) { cin >> node[i].x >> node[i].y; } for (int i = 0; i < m ;i ++) { cin >> cir[i].r; cin >> cir[i].x >> cir[i].y; } for (int i = 1; i <= n ;i ++) { for (int j = 0; j < m; j ++) { st[i][j] = dist(i, j); } } while(k --) { int a, b; cin >> a >> b; cout << (st[a]^st[b]).count() << endl; } return 0;}
O(nk/32)用bitset表示状态 用stl优化
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
