Description
Input
输入第一行包含一个正整数 n, 表示房子的总数。接下来有 n 行,分别表示每一个房子的位置。对于 i = 1, 2, .., n, 第i 个房子的坐标用一对整数 xi和yi来表示,中间用空格隔开。
Output
输出文件包含一个实数,表示平均有多少个房子被信号所覆盖,需保证输出结果与精确值的绝对误差不超过0.01。
Sample Input
4
0 2
4 4
0 0
2 0
0 2
4 4
0 0
2 0
Sample Output
3.500
HINT
3.5, 3.50, 3.500, … 中的任何一个输出均为正确。此外,3.49, 3.51,
3.499999,…等也都是可被接受的输出。
【数据范围】
100%的数据保证,对于 i = 1, 2, .., n, 第 i 个房子的坐标(xi, yi)为整数且
–1,000,000 ≤ xi, yi ≤ 1,000,000. 任何三个房子不在同一条直线上,任何四个房子不
在同一个圆上;
40%的数据,n ≤ 100;
70%的数据,n ≤ 500;
100%的数据,3 ≤ n ≤ 1,500。
直接暴力O(n^4)显然超时,所以作以下转化:
可以看出,每三个点所在的圆至少包含三个点,对答案的贡献为3;而每多包含一个点,对答案就多贡献1。
所有包含关系必定可以转化为一个一个的四边形,凸四边形对答案的贡献为14,凹四边形对答案的贡献为13。
问题转化为求有多少个凸四边形和凹四边形。
这两类四边形的数目之和一定为C(n, 4),而凹四边形的个数显然好求一些,即为求有多少个三角形中包含一点。
那么枚举中间点x,将其它点按极角排序,统计包含这个点的三角形有多少个即可。
进一步转化,设没有包含中间点的个数为X,那么包含该中间点的三角形的个数为P = C(n - 1, 3) - X。
统计X的方法:枚举其中一条线xi,再移动另一条(此时这条线的移动是单调的),保证这两条线的夹角刚好180°,那么两条线间的点任选两个作为目标三角形的顶点(三角形的第三点为当前枚举的线的端点i)即可。
设凸四边形的个数为Q,则Q = C(n, 4) - P。
答案为(14Q + 13P) / C(n, 3),经化简,即为(2Q + P) / C(n, 3) + 3。
Accode:
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <complex> using std::complex; const char fi[] = "signaling.in"; const char fo[] = "signaling.out"; const int maxN = 1510; const double zero = 1e-8; typedef complex <double> vec; typedef long long int64; vec p[maxN], tmp[maxN << 1]; int n; int64 P; void init_file() { freopen(fi, "r", stdin); freopen(fo, "w", stdout); return; } inline int getint() { int res = 0; char tmp; bool sgn = 1; do tmp = getchar(); while (!isdigit(tmp) && tmp != '-'); if (tmp == '-') { sgn = 0; tmp = getchar(); } do res = (res << 3) + (res << 1) + tmp - '0'; while (isdigit(tmp = getchar())); return sgn ? res : -res; } void readdata() { n = getint(); for (int i = 0; i < n; ++i) { int x = getint(), y = getint(); p[i] = vec((double)x, (double)y); } return; } #define otp(a, b) \ (real(a) * imag(b) - imag(a) * real(b)) inline int cmp(const void *a, const void *b) { double k = otp(*(vec *)a, *(vec *)b); return k > zero ? -1 : (k < -zero ? 1 : 0); } inline void calc(const int x) { for (int i = 0; i < x; ++i) tmp[i] = p[i] - p[x]; for (int i = x + 1; i < n; ++i) tmp[i - 1] = p[i] - p[x]; qsort(tmp, n - 1, sizeof tmp[0], cmp); for (int i = 0; i < n - 1; ++i) tmp[i + n - 1] = tmp[i]; for (int i = 0, j = 1; i < n - 1; ++i) { while (otp(tmp[i], tmp[j]) > zero) ++j; if (j - i > 2) P += (j - i - 1) * (j - i - 2) >> 1; } return; } inline int64 C(const int64 n, const int64 m) { if (n < m) return 0; if (m == 3) return n * (n - 1) * (n - 2) / 6; if (m == 4) return n * (n - 1) * (n - 2) * (n - 3) / 24; } void work() { for (int i = 0; i < n; ++i) calc(i); int64 S = (C(n, 4) << 1) - n * C(n - 1, 3) + P; //这里的P是上面所说的X。 printf("%.3lf\n", (double)S / C(n, 3) + 3); return; } int main() { init_file(); readdata(); work(); return 0; } #undef otp
第二次做:
#include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #define cross(a, b) \ (((a).x) * ((b).y) - ((b).x) * ((a).y)) typedef long long int64; const int maxN = 1510; struct vec { int64 x, y; vec(){} vec(int64 x, int64 y): x(x), y(y) {} vec operator-(const vec &b) {return vec(x - b.x, y - b.y);} }; vec p[maxN], tmp[maxN << 1]; int64 n, P; inline int64 getint() { int64 res = 0; char tmp; bool sgn = 1; do tmp = getchar(); while (!isdigit(tmp) && tmp != '-'); if (tmp == '-') {sgn = 0; tmp = getchar();} do res = (res << 3) + (res << 1) + tmp - '0'; while (isdigit(tmp = getchar())); return sgn ? res : -res; } inline int cmp(const void *a, const void *b) { int64 tmp = cross(*(vec *)a, *(vec *)b); return (tmp > 0) ? -1 : (tmp < 0) ? 1 : 0; } inline void calc(int x) { for (int i = 0; i < x; ++i) tmp[i] = p[i] - p[x]; for (int i = x + 1; i < n; ++i) tmp[i - 1] = p[i] - p[x]; qsort(tmp, n - 1, sizeof tmp[0], cmp); for (int i = 0; i < n - 1; ++i) tmp[i + n - 1] = tmp[i]; for (int i = 0, j = 1; i < n - 1; ++i) { while (cross(tmp[i], tmp[j]) > 0) ++j; if (j - i > 2) P += (int64)(j - i - 2) * (j - i - 1) >> 1; } return; } inline int64 C(int64 n, int64 m) { if (n < m) return 0; if (m == 3) return n * (n - 1) * (n - 2) / 6; if (m == 4) return n * (n - 1) * (n - 2) * (n - 3) / 24; } int main() { freopen("signaling.in", "r", stdin); freopen("signaling.out", "w", stdout); n = getint(); for (int i = 0; i < n; ++i) { int64 x = getint(), y = getint(); p[i] = vec(x, y); } for (int i = 0; i < n; ++i) calc(i); printf("%.3lf", (double)((C(n, 4) << 1) - n * C(n - 1, 3) + P) / C(n, 3) + 3); return 0; } #undef cross