|
Posted on 2009-09-18 20:10 Uriel 阅读(526) 评论(1) 编辑 收藏 引用 所属分类: POJ 、 计算几何
判断线段相交问题。。用链表做的。。(大牛们忽略下文。。) 第一次完全自己写链表。。搞了一整天。。但是真的好开心啊~~
/**//*Problem: 2653 User: Uriel Memory: 8352K Time: 750MS Language: C++ Result: Accepted*/
#include<math.h> #include<stdio.h> #include<stdlib.h> #define eps 1e-6 #define MAXN 100001
typedef struct Node{ struct Node *next; int flag; };
typedef struct point{ double x,y; int mark; };
point P1[MAXN],P2[MAXN]; int n;
//计算cross product (P1-P0)x(P2-P0) double xmult(point p1,point p2,point p0) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); }
//判两点在线段异侧,点在线段上返回0 int opposite_side(point p1,point p2,point l1,point l2) { return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps; }
//判两线段相交,不包括端点和部分重合 int intersect_ex(point u1,point u2,point v1,point v2) { return opposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2); }
void creat(Node *L) { Node *p;
p=(Node *)malloc(sizeof(Node)); if(p==NULL)return ; p->flag=P1[0].mark; p->next=NULL; L->next=p; } void Del(Node *L,int i) //删除结点 { Node *p,*q; p=L->next; q=L; while(p) { // printf("flag=%d i=%d\n",p->flag,i); if(p->flag==i) { q->next=p->next; p=q; break; } q=p; p=p->next; } return ; }
void Insert(Node *L,int a) //插入结点 { Node *p,*s; int k=1; s=(Node *)malloc(sizeof(Node)); if(s==NULL)return ; p=L; while(p->next!=NULL) { p=p->next; } p->next=s; s->next=NULL; s->flag=P1[a].mark; return ; }
void ADD(Node *S,int i) { Insert(S,i); Node *p; p=S->next; while(p->next!=NULL) { // printf("flag=%d\n",p->flag); if(intersect_ex(P1[i],P2[i],P1[p->flag-1],P2[p->flag-1])) //如果该直线与前面几个线段有交点,则删除代表前面那些线段的结点 { Del(S,p->flag); } p=p->next; } }
void Print(Node *L) //遍历链表,打印 { Node *p; p=L->next; printf("Top sticks:"); if(p) { printf(" %d",p->flag); p=p->next; } while(p) { printf(", %d",p->flag); p=p->next; } }
void Free(Node *L) { Node *p, *q;
p=L->next; while (p != NULL) { q= p; p= p->next; free(q); } }
int main() { Node Q;
while(1) { scanf("%d",&n); if(!n)break; for(int i=0;i<n;i++) { scanf("%lf %lf %lf %lf",&P1[i].x,&P1[i].y,&P2[i].x,&P2[i].y); P1[i].mark=i+1; if(i==0)creat(&Q); //第一个输入值,创建链表 else ADD(&Q,i); } Print(&Q); printf(".\n"); Free(&Q); Q.next=NULL; } system("PAUSE"); return 0; }
Feedback
# re: POJ 2653 Pick-up sticks---计算几何[未登录] 回复 更多评论
2009-09-23 23:02 by
汗死 我还以为这题要用NlogN的算法导论上的算法,没想到暴力才500ms+...
|