这一节TEXT介绍的是计算几何的内容。关于计算几何的内容,还要分开来具体阐述,难点是凸包。
第一题:
题目大意:逆时针给定若干个点,判断这些点能否构成一个多边形,并且给定一个观察点,求此点可观察到的线段
算法:枚举+计算几何
这道题目很纠结,花了半天时间研究MAIGO的代码,大致理解了,但并不能完全消化。
int cnt = 0; for (int i = 1; i <= n; i++) cnt += vis[i];
printf("%d/n", cnt);
for (int i = 1; i <= n-2; i++) if (vis[i]) printf("%d %d %d %d/n", x[i], y[i], x[i+1], y[i+1]);
if (vis[n]) printf("%d %d %d %d/n", x[1], y[1], x[n], y[n]);
if (vis[n-1]) printf("%d %d %d %d/n", x[n-1], y[n-1], x[n], y[n]);
}
return 0;
}
/*point to the next point especially for x = n with 1 next */
int next(int x) {
if (x < n) return x+1; else return 1;
}
int sgn(int x) {
if (x > 0) return 1;
if (x == 0) return 0;
if (x < 0) return -1;
}
/*get the dot-product at the start point (xa, ya) */
int scalar(int xa, int ya, int xb, int yb, int xc, int yc) {
int x1 = xb-xa, y1 = yb-ya;
int x2 = xc-xa, y2 = yc-ya;
return x1 * x2 + y1 * y2;
}
/*get the cross-product at the start point(xa, ya), the direction from ab -> ac */
int cross(int xa, int ya, int xb, int yb, int xc, int yc) {
int x1 = xb-xa, y1 = yb-ya;
int x2 = xc-xa, y2 = yc-ya;
return x1 * y2 - x2 * y1;
}
/*judge whether the four point intersect each other inside*/
bool intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
return (sgn(cross(x1, y1, x2, y2, x3, y3)) * sgn(cross(x1, y1, x2, y2, x4, y4)) < 0) &&
(sgn(cross(x3, y3, x4, y4, x1, y1)) * sgn(cross(x3, y3, x4, y4, x2, y2)) < 0);
}
/*get the Euclidean distance*/
double distance(double x1, double y1, double x2, double y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
/*judge whether it can form a fence*/
bool anycross() {
for (int i = 1; i <= n-2; i++)
for (int j = i+2; j <= n; j++)
if (intersect(x[i], y[i], x[next(i)], y[next(i)], x[j], y[j], x[next(j)], y[next(j)])) return true;
return false;
}
/*get the angle from tangent */
double angle(int x, int y) {
if (x == 0) {
if (y > 0) return pi/2; else return pi*1.5;//tangent not exist
} else {
double t = atan(1.0*y/x);//NOTICE THE TYPE!!!!
if (x > 0) {
if (y > 0) return t; else return pi*2+t;
} else return t+pi;
}
}
void look(double angle) {
double min = 1e30, alpha, beta;
int x1, y1, x2, y2, v = 0;
for (int i = 1; i <= n; i++) {
/**********************************************************************
**(x1, y1) is in the lower position, (x2, y2) is in the higher position
**alpha is the angle of (x1, y1), beta is the angle of (x2, y2)
**make sure that angle between alpha and beta
**In the triangle ABC with D in a BC, S(ABD)/S(ACD) = Sin(beta-angle) * AD * AB / (Sin(angle - alpha) * AD * AC) = DB / DC = t
**the position of D can be worked out with (x1, y1) and (x2, y2),so the distance of PD is known
**we get the minimal distance as the first seeing line
***********************************************************************/
if (cross(px, py, x[i], y[i], x[next(i)], y[next(i)]) > 0) {
x1 = x[i]; y1 = y[i]; x2 = x[next(i)]; y2 = y[next(i)]; alpha = a[i]; beta = a[next(i)];
} else {
x1 = x[next(i)]; y1 = y[next(i)]; x2 = x[i]; y2 = y[i]; alpha = a[next(i)]; beta = a[i];
}
if (sin(angle - alpha) > 0 && sin(beta - angle) > 0) {
double t = sin(angle - alpha) / sin(beta - angle) * distance(px, py, x1, y1) / distance(px, py, x2, y2);
double d = distance(px, py, (x1+t*x2)/(1+t), (y1+t*y2)/(1+t));
if (d < min) { min = d; v = i; }
}
}
if (min < 1e30) vis[v] = true;
}
第二题:American Heritage
算法:中序遍历
第三题:Electric Fence
算法:皮克定理
第四题:Raucaus Rockers
算法1:枚举 + 位运算 + 剪枝
算法2:DP(经典)
以下来子NOCOW网站上的写得很好的一个程序,值得学习
#include <cstdio>
#define MAXN 21
FILE *fin = fopen("rockers.in", "r");
FILE *fout = fopen("rockers.out", "w");
int max[MAXN], g[MAXN][MAXN], t[MAXN];
int main()
{
int N, T, M;
fscanf(fin, "%d%d%d", &N, &T, &M);
for (int i = 1; i <= N; i++)
fscanf(fin, "%d", &t[i]);
for (int i = 1; i <= N; i++)
for (int j = M; j >= 1; j--)
{
g[j][0] = max[j - 1];
for (int v = T; v >= t[i]; v--)
{
if (g[j][v] <= g[j][v - t[i]] + 1)
g[j][v] = g[j][v - t[i]] + 1;
if (g[j][v] > max[j]) max[j] = g[j][v];
}
}
fprintf(fout, "%d/n", max[M]);
return 0;
}
**DP的题目思路不是很清晰,只会基本的形式,有必要认真研读DD_ENGI的《背包九讲》。
**计算几何的功底很薄弱,需要针对性加强