首页 > 代码库 > UVA 11529 - Strange Tax Calculation(计数问题)
UVA 11529 - Strange Tax Calculation(计数问题)
题目链接:11529 - Strange Tax Calculation
题意:平面上n个建筑物,3个建筑物可以组成一个三角形,计算平均每个三角形内有多少个点
思路:问题等价于,求凹四边形的占所有四边形的比例,用O(n^2)的算法,跟
HDU 3629 Convex
这题是一个道理代码:
#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; const double eps = 1e-9; const double pi = acos(-1.0); const int N = 1225; int t, n, tn; struct Point { double x, y; void read() { scanf("%lf%lf", &x, &y); } } p[N]; double r[2 * N]; double C(int n, int m) { if (m > n) return 0; double ans = 1; for (int i = 0; i < m; i++) ans = ans * (n - i) / (i + 1); return ans; } double cal(Point a, Point b) { return atan2(b.y - a.y, b.x - a.x); } double solve(int num) { tn = 0; double ans = 0; for (int i = 0; i < n; i++) { if (i == num) continue; r[tn++] = cal(p[num], p[i]); } sort(r, r + tn); int j = 1; for (int i = 0; i < tn; i++) r[i + tn] = r[i] + 2 * pi; for (int i = 0; i < tn; i++) { while (fabs(r[j] - r[i]) - pi < -eps) j++; ans += C(j - i - 1, 2); } return C(tn, 3) - ans; } int main() { int cas = 0; while (scanf("%d", &n) && n) { double ans = 0; for (int i = 0; i < n; i++) p[i].read(); for (int i = 0; i < n; i++) { ans += solve(i); } printf("City %d: %.2lf\n", ++cas, ans / C(n, 3)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。