UVa 11529 (计数) Strange Tax Calculation

枚举一个中心点,然后将其他点绕着这个点按照极角排序。

统计这个中心点在外面的三角形的个数,然后用C(n-1, 3)减去这个数就是包含这个点的三角形的数量。

然后再枚举一个起点L,终点为弧度小于π的点R。

在[L+1, R]任取两点再加上起点,这些三角形都不包含中心点。

 #include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; const int maxn = + ;
const double PI = acos(-1.0); struct Point
{
int x, y;
}p[maxn];
double ang[maxn * ];
typedef Point Vector; double inline C2(int n) { return n * (n-) / ; }
double inline C3(int n) { return n * (n-) / * (n-) / ; }
double solve(int n)
{
double s = C3(n-), ans = ;
for(int i = ; i < n; i++)
{//枚举中心点
int k = ;
for(int j = ; j < n; j++) if(j != i)
{
ang[k] = atan2(p[j].x-p[i].x, p[j].y-p[i].y);
ang[k + n - ] = ang[k] + 2.0 * PI;
k++;
}
k = *(n-);
sort(ang, ang + k);
int L = , R = ;
double t = ;
for(L = ; L < n-; L++)
{
double temp = ang[L] + PI;
while(temp > ang[R]) R++;
t += C2(R - L - );
}
ans += s - t;
}
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); int n, kase = ;
while(scanf("%d", &n) == && n)
{
for(int i = ; i < n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
double ans = solve(n) / C3(n);
printf("City %d: %.2f\n", ++kase, ans);
} return ;
}

代码君

上一篇:Cardinality Feedback


下一篇:分析oracle的执行计划(explain plan)并对对sql进行优化实践