题目1： POJ 2318 TOYS
题目大意：
给一个有n个挡板的盒子，从左到右空格编号为0...n。有好多玩具，问每个玩具在哪个空格里面。
算法讨论：
直接叉积判断就可以。注意在盒子的边界上面也算在盒子里面。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int M = + ;
typedef long long ll; int n, m, a, b, c, d;
int vi[M], tim = , num[M]; struct Line {
int zx, zy, yx, yy;
}l[M]; struct Point {
int x, y;
bool operator < (const Point &h) const {
if(h.x == x) return y < h.y;
return x < h.x;
}
}p[M]; ll cross(int i, int j) {
return 1LL * (l[i].zx - p[j].x) * (l[i].yy - p[j].y) - 1LL * (l[i].yx - p[j].x) * (l[i].zy - p[j].y);
}
#define ONLINE_JUDGE int main() {
#ifndef ONLINE_JUDGE
freopen("t.txt", "r", stdin);
freopen("t.out", "w", stdout);
#endif int u, v; while(scanf("%d", &n) && n) {
scanf("%d%d%d%d%d", &m, &a, &b, &c, &d);
++ tim;
memset(num, , sizeof num);
for(int i = ; i <= n; ++ i) {
scanf("%d%d", &u, &v);
l[i].zx = u; l[i].zy = b;
l[i].yx = v; l[i].yy = d;
}
l[].zx = l[].yx = a;
l[].zy = b; l[].yy = d;
l[n + ].zx = l[n + ].yx = c;
l[n + ].zy = b; l[n + ].yy = d;
for(int i = ; i <= m; ++ i) {
scanf("%d%d", &p[i].x, &p[i].y);
}
for(int i = ; i < n + ; ++ i) {
for(int j = ; j <= m; ++ j) {
if(vi[j] == tim) continue;
if(p[j].y == b) {
if(p[j].x >= l[i].zx && p[j].x <= l[i + ].zx) {
vi[j] = tim;
num[i] ++;
}
}
else if(p[j].y == d) {
if(p[j].x >= l[i].yx && p[j].x <= l[i + ].yx) {
vi[j] = tim;
num[i] ++;
}
}
else if(i == && p[j].x == a) {
vi[j] = tim;
num[] ++;
}
else if(i == n && p[j].x == c) {
vi[j] = tim;
num[n] ++;
}
else if(1LL * cross(i, j) * cross(i + , j) < ) {
vi[j] = tim;
num[i] ++;
}
}
}
for(int i = ; i < n + ; ++ i) {
printf("%d: %d\n", i, num[i]);
}
puts("");
} #ifndef ONLINE_JUDGE
fclose(stdin); fclose(stdout);
#endif
return ;
}
poj 2318
题目2： POJ 2398 Toys
题目大意：
同上。不过不同的是，这里面的挡板输入是没有顺序的，而且问的是有t个玩具的格子有几个。
算法讨论：
上个题小小变动一下就可以了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int M = + ;
typedef long long ll; int n, m, a, b, c, d;
int vi[M], tim = , num[M], out[M]; struct Line {
int zx, zy, yx, yy;
bool operator < (const Line &h) const {
int lx1 = max(zx, yx), mx1 = min(zx, yx);
int lx2 = max(h.zx, h.yx), mx2 = min(h.zx, h.yx); if(mx2 == mx1) {
return lx1 < lx2;
}
return mx1 < mx2;
}
}l[M]; struct Point {
int x, y;
bool operator < (const Point &h) const {
if(h.x == x) return y < h.y;
return x < h.x;
}
}p[M]; ll cross(int i, int j) {
return 1LL * (l[i].zx - p[j].x) * (l[i].yy - p[j].y) - 1LL * (l[i].yx - p[j].x) * (l[i].zy - p[j].y);
}
#define ONLINE_JUDGE int main() {
#ifndef ONLINE_JUDGE
freopen("t.txt", "r", stdin);
freopen("t.out", "w", stdout);
#endif int u, v; while(scanf("%d", &n) && n) {
scanf("%d%d%d%d%d", &m, &a, &b, &c, &d);
++ tim;
memset(num, , sizeof num);
memset(out, , sizeof out);
for(int i = ; i <= n; ++ i) {
scanf("%d%d", &u, &v);
l[i].zx = u; l[i].zy = b;
l[i].yx = v; l[i].yy = d;
}
sort(l + , l + n + );
l[].zx = l[].yx = a;
l[].zy = b; l[].yy = d;
l[n + ].zx = l[n + ].yx = c;
l[n + ].zy = b; l[n + ].yy = d;
for(int i = ; i <= m; ++ i) {
scanf("%d%d", &p[i].x, &p[i].y);
}
for(int i = ; i < n + ; ++ i) {
for(int j = ; j <= m; ++ j) {
if(vi[j] == tim) continue;
if(p[j].y == b) {
if(p[j].x >= l[i].zx && p[j].x <= l[i + ].zx) {
vi[j] = tim;
num[i] ++;
}
}
else if(p[j].y == d) {
if(p[j].x >= l[i].yx && p[j].x <= l[i + ].yx) {
vi[j] = tim;
num[i] ++;
}
}
else if(i == && p[j].x == a) {
vi[j] = tim;
num[] ++;
}
else if(i == n && p[j].x == c) {
vi[j] = tim;
num[n] ++;
}
else if(1LL * cross(i, j) * cross(i + , j) < ) {
vi[j] = tim;
num[i] ++;
}
}
}
for(int i = ; i < n + ; ++ i) {
out[num[i]] ++;
}
puts("Box");
for(int i = ; i <= m; ++ i) {
if(out[i])
printf("%d: %d\n", i, out[i]);
}
} #ifndef ONLINE_JUDGE
fclose(stdin); fclose(stdout);
#endif
return ;
}
poj 2398
题目3： POJ 1654 Area
题目大意：
给一个数字序列，每个数字都代表向特定的方向走。求数字围成的多边形的面积。数据保证合法。
算法讨论：
直接做就行。注意输出的时候，分类讨论下就可以了。而且注意内存，不能把点存下来，要边读入边计算。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath> using namespace std; const int N = + ; int len, cnt;
char str[N];
int dx[]={, , , , , , , -, -, -};
int dy[]={, -, , , -, , , -, , }; double cross(double a, double b, double c, double d) {
return a * d - b * c;
} int main() {
int t; scanf("%d", &t); while(t --) {
scanf("%s", str + );
len = strlen(str + ); double last_x = , last_y = ;
double area = ; for(int i = ; i <= len; ++ i) {
int q = str[i] - ''; if(q == ) {
break;
}
area += cross(last_x, last_y, last_x + dx[q], last_y + dy[q]);
last_x += dx[q]; last_y += dy[q];
} if((int)area & )
printf("%.0lf.5\n", floor(fabs(area) / ));
else
printf("%.0lf\n", fabs(area) / );
}
return ;
}
POJ 1654
题目4： POJ 1269 Intersecting Lines
题目大意：
给出直线对，判断这对直线的关系：平行，重合或者相交。
算法讨论：
假设直线1的两个点编号为1，2，直线2的两个点编号为3，4，如果 1，2，4的叉积为0， 1，2，3的叉积为0，则说明重合。
如果不重合，用两点式算斜率，为了避免除0错误，把两边除法比较变形为乘法。
如果不重合也不平行，就相交，用分点定理找交点。我的代码中只有规范相交的部分。具体代码请见刘汝佳《算法艺术与信息学竞赛》P357页。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath> using namespace std; const double eps = 1e-; int n; struct Point {
double a, b;
Point(double _a = , double _b = ):
a(_a), b(_b) {}
}c[]; double cross(int i, int j, int k) {
return (c[i].a - c[k].a) * (c[j].b - c[k].b) - (c[j].a - c[k].a) * (c[i].b - c[k].b);
} int dcmp(double s) {
return s > eps ? : (s < -eps ? - : );
} void solve() {
if(fabs(cross(, , )) <= eps && fabs(cross(, , )) <= eps) puts("LINE");
else if((c[].b - c[].b) * (c[].a - c[].a) == (c[].a - c[].a) * (c[].b - c[].b))
puts("NONE");
else {
double s1 = cross(, , ), s2 = cross(, , );
double x = (c[].a * s2 - c[].a * s1) / (s2 - s1);
double y = (c[].b * s2 - c[].b * s1) / (s2 - s1); printf("POINT %.2f %.2f\n", x, y);
}
} int main() {
double a, b; puts("INTERSECTING LINES OUTPUT");
scanf("%d", &n);
for(int i = ; i <= n; ++ i) {
for(int j = ; j <= ; ++ j) {
scanf("%lf%lf", &a, &b);
c[j] = Point(a, b);
}
solve();
}
puts("END OF OUTPUT");
return ;
}
POJ 1269
题目5： POJ 1113 Wall
题目大意：
求给出点集的凸包长度+一个半径为r的圆的周长和。
算法讨论：
看了下面这个图，你就什么都明白了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath> #define pi 3.1415926535 using namespace std; const int N = + ;
const double eps = 1e-; int n, l;
double ans = ; struct Point {
double x, y;
}p[N], st[N]; double dist(Point a, Point b) {
return sqrt(pow(a.x - b.x, ) + pow(a.y - b.y, ));
} double cross(Point a, Point b, Point c) {
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
} bool cmp(Point a, Point b) {
if(cross(a, b, p[]) == )
return dist(a, p[]) < dist(b, p[]);
return cross(a, b, p[]) > ;
} void Graham() {
int top = , k = ; for(int i = ; i < n; ++ i) {
if(p[i].x < p[k].x || (p[i].x == p[k].x && p[i].y < p[k].y))
k = i;
}
swap(p[k], p[]);
sort(p + , p + n, cmp);
st[] = p[]; st[] = p[]; st[] = p[];
for(int i = ; i < n; ++ i) {
while(top && cross(p[i], st[top], st[top - ]) >= ) top --;
st[++ top] = p[i];
}
st[++ top] = p[];
for(int i = ; i < top; ++ i)
ans += dist(st[i], st[i + ]);
} int main() {
scanf("%d%d", &n, &l);
for(int i = ; i < n; ++ i) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
Graham();
printf("%.0f", (double) ans + (double) * pi * l);
return ;
}
POJ 1113
题目6： POJ 3304 Segments
题目大意：
给出N个线段，是否有存在一条直线与所有线段都相交。
算法讨论：
这个直线一定经过线段的两个端点。所以我们枚举端点然后判断是否与每条线段相交即可。
判断相交的方法，用跨立实验。如果直线上的两个点与线段的两个点的叉积大于0，说明相交。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int N = + ;
const double eps = 1e-; int n, cnt; struct Line {
double a, b, c, d;
}l[N];
struct Point {
double x, y;
}p[N<<];
double cross(int i, int j, int k) {
double t1 = (p[i].x - l[k].a) * (p[j].y - l[k].b) - (p[j].x - l[k].a) * (p[i].y - l[k].b);
double t2 = (p[i].x - l[k].c) * (p[j].y - l[k].d) - (p[j].x - l[k].c) * (p[i].y - l[k].d);
return t1 * t2;
}
int main() {
int t; scanf("%d", &t); while(t --) {
cnt = ;
scanf("%d", &n);
for(int i = ; i <= n; ++ i) {
scanf("%lf%lf%lf%lf", &l[i].a, &l[i].b, &l[i].c, &l[i].d);
p[++ cnt].x = l[i].a; p[cnt].y = l[i].b;
p[++ cnt].x = l[i].c; p[cnt].y = l[i].d;
}
if(n == || n == ) {
puts("Yes!");
continue;
}
for(int i = ; i <= cnt; ++ i) {
for(int j = i + ; j <= cnt; ++ j) {
if(fabs(p[i].x - p[j].x) < eps && fabs(p[i].y - p[j].y) < eps) continue;
for(int k = ; k <= n; ++ k) {
if(cross(i, j, k) > ) {
break;
}
if(k == n) {
puts("Yes!");
goto A;
}
}
}
}
puts("No!");
A:;
} return ;
}
POJ 3304
题目7： POJ 2187 Beauty Conteset
题目大意：
求平面点集最远点距离平方。
算法讨论：
旋转卡壳直接上吧。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath> using namespace std; const int N = + ; int n, top = ;
double ans; struct Point {
double x, y;
}p[N], st[N]; double dist(Point a, Point b) {
return sqrt(pow(a.x - b.x, ) + pow(a.y - b.y, ));
} double cross(Point a, Point b, Point c) {
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
} double cal(Point a, Point b) {
return pow(a.x - b.x, ) + pow(a.y - b.y, );
} bool cmp(Point a, Point b) {
if(cross(a, b, p[]) == )
return dist(a, p[]) < dist(b, p[]);
return cross(a, b, p[]) > ;
} void Graham() {
int k = ; for(int i = ; i < n; ++ i)
if(p[i].x < p[k].x || (p[i].x == p[k].x && p[i].y < p[k].y))
k = i;
swap(p[], p[k]);
sort(p + , p + n, cmp);
st[] = p[]; st[] = p[]; st[] = p[];
for(int i = ; i < n; ++ i) {
while(top && cross(p[i], st[top], st[top - ]) >= ) top --;
st[++ top] = p[i];
}
st[++ top] = p[];
} void rotate() {
int q = ; for(int i = ; i < top; ++ i) {
while(cross(st[i + ], st[q + ], st[i]) > cross(st[i + ], st[q], st[i]))
q = (q + ) % top;
ans = max(ans, max(cal(st[i], st[q]), cal(st[i + ], st[q + ])));
}
} int main() {
scanf("%d", &n);
for(int i = ; i < n; ++ i) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
Graham();
rotate();
printf("%.0f", ans);
return ;
}
POJ 2187
题目8： POJ 1584 A Round Peg in a Ground Hole
题目大意：
给一个圆和一些点。你要做三件事:判断这些点是否组成一个凸多边形。 圆的圆心是否在多边形内。 圆是否在凸多边形内。
算法讨论：
对于第一个件事，我们直接做Graham然后看有多少个点在凸包上。注意排序的时候，如果三个点在一个竖线上的情况要在cmp函数里面判断一下。
对于第二件事，由于这是一个凸多边形，所以我们用回转角法来判断是否在多边形内。注意这里eps不要取的太小，否则会被卡精度。
对于第三件事，最简单的，直接算距离，注意相切的情况也算在多边形内部。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath> #define pi 3.1415926535 using namespace std; const int N = + ;
const double eps = 1e-; int n, top = ;
double cx, cy, cr; struct Point {
double x, y;
}p[N], st[N]; double dist(Point a, Point b) {
return sqrt(pow(a.x - b.x, ) + pow(a.y - b.y, ));
} double cross(Point a, Point b, Point c) {
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
} bool cmp(Point a, Point b) {
if(cross(a, b, p[]) == ) {
if(a.x == b.x && a.x == p[].x)
return dist(a, p[]) > dist(b, p[]);
else
return dist(a, p[]) < dist(b, p[]);
}
return cross(a, b, p[]) > ;
} void Graham() {
int k = ; top = ;
for(int i = ; i < n; ++ i) {
if(p[i].x < p[k].x || (p[i].x == p[k].x && p[i].y < p[k].y))
k = i;
}
swap(p[k], p[]);
sort(p + , p + n, cmp);
st[] = p[]; st[] = p[]; st[] = p[];
for(int i = ; i < n; ++ i) {
while(top && cross(p[i], st[top], st[top - ]) > ) top --;
st[++ top] = p[i];
}
st[++ top] = p[];
} double len(int i) {
return sqrt(pow(st[i].x - cx, ) + pow(st[i].y - cy, ));
} double cal(int i, int j) {
double t1 = (st[i].x - cx) * (st[j].x - cx) + (st[i].y - cy) * (st[j].y - cy);
double t2 = len(i) * len(j); return t1 / t2;
} int main() {
while() {
scanf("%d", &n);
if(n < ) break;
scanf("%lf%lf%lf", &cr, &cx, &cy);
for(int i = ; i < n; ++ i) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
Graham();
if(top != n) {
puts("HOLE IS ILL-FORMED");
continue;
} double tmp = ;
bool flag = false; for(int i = ; i < top; ++ i) {
tmp += (double)acos(cal(i, i + )) * / pi;
}
if(fabs(tmp - 360.00000) > eps) {
puts("PEG WILL NOT FIT");
continue;
}
for(int i = ; i < top; ++ i) {
tmp = (st[i].x - cx) * (st[i + ].y - cy) - (st[i + ].x - cx) * (st[i].y - cy);
tmp = fabs(tmp);
tmp = tmp / dist(st[i], st[i + ]);
if(tmp - cr < -eps) {
flag = true;
break;
}
}
if(flag) {
puts("PEG WILL NOT FIT");
}
else {
puts("PEG WILL FIT");
}
}
return ;
}
POJ 1584
题目9： POJ 2079 Triangle
题目大意：
求点集中面积最大的三角形面积。
算法讨论：
类似旋转卡壳的算法。感觉这是个模板题。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int N = + ; int n, top;
double ans = ; struct Point {
double x, y;
}p[N], st[N]; double dist(Point a, Point b) {
return sqrt(pow(a.x - b.x, ) + pow(a.y - b.y, ));
} double cross(Point a, Point b, Point c) {
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
} bool cmp(Point a, Point b) {
if(cross(a, b, p[]) == )
return dist(a, p[]) < dist(b, p[]);
return cross(a, b, p[]) > ;
} void Graham() {
int k = ; top = ; for(int i = ; i < n; ++ i) {
if(p[i].x < p[k].x || (p[i].x == p[k].x && p[i].y < p[k].y))
k = i;
}
swap(p[], p[k]);
sort(p + , p + n, cmp);
st[] = p[]; st[]= p[]; st[] = p[];
for(int i = ; i < n; ++ i) {
while(top && cross(p[i], st[top], st[top - ]) >= )top --;
st[++ top] = p[i];
}
st[++ top] = p[];
} void rotate_triangle() {
int i, j, k, kk; for(i = ; i < top; ++ i) {
j = (i + ) % top;
k = (j + ) % top;
while(k != i && cross(st[i], st[j], st[k]) < cross(st[i], st[j], st[k + ]))
k = (k + ) % top;
if(k == i) continue;
kk = (k + ) % top;
while(j != kk && k != i) {
ans = max(ans, fabs(cross(st[i], st[j], st[k])));
while(k != i && cross(st[i], st[j], st[k]) < cross(st[i], st[j], st[k + ]))
k = (k + ) % top;
j = (j + ) % top;
}
}
} int main() {
while(scanf("%d", &n) && n > ) {
ans = ;
for(int i = ; i < n; ++ i) {
scanf("%lf%lf", &p[i].x, &p[i].y);
}
Graham();
rotate_triangle();
printf("%.2f\n", (double) ans / );
} return ;
}
POJ 2079
题目10： POJ 2653 Pick-up sticks
题目大意：
给一坨线段，问哪里线段可以被看到。
算法讨论：
在网上看到了两种解法，一个是O(N^2)的暴力，但是不知道为什么对于10W的数据可以跑过。就是枚举每一个线段i，如果有线段和其相交，
那么这个线段就是不可见。
另一个解法就是对于当前线段，判断其是否与队列中的线段有交点，如果有，把有交点的那个线段出队，把这个入队，否则两个一起入队。
看样子是一样的方法啊。我的代码还是没有不规范判断相交的部分。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath> using namespace std; const int N = + ;
const double eps = 1e-; int n;
bool flag[N]; struct Point {
double x, y;
Point(double _x = , double _y = ):
x(_x), y(_y) {}
};
struct Line {
Point A, B;
}l[N]; double cross(Point a, Point b, Point c) {
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
} int dcmp(double x) {
return x > eps ? : (x < -eps ? - : );
} int segcross(Point a, Point b, Point c, Point d) {
int d1, d2, d3, d4; d1 = dcmp(cross(a, b, c));
d2 = dcmp(cross(a, b, d));
d3 = dcmp(cross(c, d, a));
d4 = dcmp(cross(c, d, b)); if((d1 ^ d2) == - && (d3 ^ d4) == -)
return ;
return ;
} int main() {
double a, b, c, d; while(scanf("%d", &n) && n) {
for(int i = ; i <= n; ++ i ) {
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
l[i].A = (Point){a, b};
l[i].B = (Point){c, d};
flag[i] = true;
}
for(int i = ; i <= n; ++ i) {
for(int j = i + ; j <= n; ++ j) {
if(segcross(l[i].A, l[i].B, l[j].A, l[j].B)) {
flag[i] = false;
break;
}
}
}
bool tmp = false; printf("Top sticks: ");
for(int i = ; i <= n; ++ i) {
if(flag[i]) {
if(!tmp) {
printf("%d", i);
tmp = true;
}
else {
printf(", %d", i);
}
}
}
puts(".");
} return ;
}
POJ 2653