計(jì)算幾何入門題（更新中……）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1696Space Ant用到叉積，點(diǎn)積。這個題的代碼稍微改改，貌似可以認(rèn)為是凸包的o(n^2)算法，即卷包心菜。
1
//1696_SpaceAnt ~ alpc02
2#include <math.h>
3#include <algorithm>
4using namespace std;
5
6const int N = 55;
7
8const double PRECISION = 1e-8;
9int dblcmp(double d) 
{
10
return (fabs(d) < PRECISION) ? 0:(d>0 ? 1:-1);
11
}
12struct Point {
13 double x, y;
14};
15double dotdet(double x1, double y1, double x2, double y2) {
16 return x1*x2 + y1*y2;
17} //點(diǎn)積
18double det(double x1, double y1, double x2, double y2) {
19 return x1*y2 - x2*y1;
20} //叉積
21int cross(const Point &a, const Point &c, const Point &d) {
22 return dblcmp( det(a.x-c.x, a.y-c.y, d.x-c.x, d.y-c.y) );
23} //右手螺旋定則，1——a在cd右側(cè)，-1——a在cd左側(cè)，0——三點(diǎn)共線
24bool between(const Point &a, const Point &c, const Point &d) {
25 return dblcmp( dotdet(c.x-a.x, c.y-a.y, d.x-a.x, d.y-a.y) ) != 1;
26} //在cross(a,b,c)==0的基礎(chǔ)上，可判斷點(diǎn)a是否在cd內(nèi)部
27double Min(double a, double b){return a<b ? a:b; }
28
29Point a[N];
30bool f[N];
31int main() {
32 freopen("in", "r", stdin);
33 int Ca;
34 scanf("%d", &Ca);
35
36 int n, i, j, k;
37 int now, temp;
38
while(Ca--) {
39 scanf("%d",&n);
40 a[0].x = 0;
41 a[0].y = 1e10;
42 for(i=1; i<=n; i++) {
43 scanf("%d", &k);
44 scanf("%lf %lf", &a[k].x, &a[k].y);
45 a[0].y = Min(a[0].y, a[k].y);
46
}
47 memset(f, false, sizeof(f));
48
49 now = 0;
50 printf("%d", n);
51 for(i=1; i<=n; i++) {
52 k = -1;
53 for(j=1; j<=n; j++)
54 if(!f[j]) {
55 if(k == -1) k = j;
56 else {
57 temp = cross(a[j], a[now], a[k]);
58 if( (temp == 1) || (temp == 0 && between(a[j], a[now], a[k])) )
59 k = j;
60 }
61 }
62 now = k;
63 printf(" %d", now);
64 f[now] = true;
65 }
66 printf("\n");
67 }
68 return 0;
69}
70判斷兩直線平行、重合還是相交，如果相交，求出交點(diǎn)。
1//1269_IntersectingLines ~ alpc02
2#include <math.h>
3#include <algorithm>
4using namespace std;
5
6const double PRECISION = 1e-8;
7struct Point {
8 double x, y;
9};
10int dblcmp(double d) {
11 return (fabs(d) < PRECISION) ? 0:(d>0 ? 1:-1);
12} //三叉口函數(shù)，避免精度誤差
13double det(double x1, double y1, double x2, double y2) {
14 return x1*y2 - x2*y1;
15} //叉積
16int cross(const Point &a, const Point &c, const Point &d) {
17 return dblcmp( det(a.x-c.x, a.y-c.y, d.x-c.x, d.y-c.y) );
18} //右手螺旋定則，1——a在cd右側(cè)，-1——a在cd左側(cè)，0——三點(diǎn)共線
19void intersect(const Point &a, const Point &b, const Point &c, const Point &d, Point &e) {
20 double sc, sd;
21 sc = fabs( det(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y) );
22 sd = fabs( det(b.x-a.x, b.y-a.y, d.x-a.x, d.y-a.y) );
23 e.x = (sc * d.x + sd * c.x) / (sc + sd);
24 e.y = (sc * d.y + sd * c.y) / (sc + sd);
25} //規(guī)范相交時(shí)，求交點(diǎn)坐標(biāo)
26void lineIntersect(Point a, Point b, Point c, Point &d, Point &e) {
27 double temp = 1000;
28 a.x += (a.x - b.x) * temp;
29 a.y += (a.y - b.y) * temp;
30 b.x += (b.x - a.x) * temp;
31 b.y += (b.y - a.y) * temp;
32 c.x += (c.x - d.x) * temp;
33 c.y += (c.y - d.y) * temp;
34 d.x += (d.x - c.x) * temp;
35 d.y += (d.y - c.y) * temp;
36 intersect(a, b, c, d, e);
37} //先把直線先延長得足夠長
38int main() {
39 freopen("in", "r", stdin);
40 int Ca;
41 Point a, b, c, d, e;
42 printf("INTERSECTING LINES OUTPUT\n");
43 scanf("%d", &Ca);
44 while(Ca--) {
45 scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
46 if(dblcmp( det(a.x-b.x, a.y-b.y, c.x-d.x, c.y-d.y) ) != 0) {
47 printf("POINT ");
48 lineIntersect(a, b, c, d, e);
49 printf("%.2lf %.2lf\n", e.x, e.y);
50 }
51 else {
52 if(cross(a,c,d) == 0)
53 printf("LINE\n");
54 else
55 printf("NONE\n");
56 }
57 }
58 printf("END OF OUTPUT\n");
59 return 0;
60}
61給定n條線段，問是否存在一條直線和每條線段都相交
如果存在，則肯定可以把這條直線調(diào)整為經(jīng)過所有線段端點(diǎn)中的某兩個。
這樣的話，可枚舉這兩個端點(diǎn)，然后判斷直線和線段相交。
相關(guān)代碼可參考
http://www.shnenglu.com/shiming413/archive/2007/08/22/30617.html
posted on 2007-08-22 18:28
LSM 閱讀(1383)
評論(2) 編輯 收藏 引用 所屬分類:
計(jì)算幾何