|
|
Posted on 2009-09-18 20:10 Uriel 阅读(528) 评论(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+...
|