|
|
Posted on 2009-09-18 20:10 Uriel 閱讀(533) 評論(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+...
|