注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2653 Pick-up sticks 线段相交判断  

2011-04-30 21:54:26|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://poj.org/problem?id=2653
顺序的在地上扔一些细棒,求最后没有被压的细棒。
我是用list容器存储,枚举过去,有被压的就删除,效率比较底,运行800多ms。

                           
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<cmath>
#include<list>
using namespace std;
struct point
{
double x,y;
};
struct line
{
point a,b;
int num;
};
list<line> dlist;
double multi(point p0,point p1,point p2)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool is(point s1,point e1,point s2,point e2) //判断线段是否相交 
{
return (max(s1.x,e1.x)>=min(s2.x,e2.x))&&
  (max(s2.x,e2.x)>=min(s1.x,e1.x))&&
  (max(s1.y,e1.y)>=min(s2.y,e2.y))&&
  (max(s2.y,e2.y)>=min(s1.y,e1.y))&&
  (multi(s1,s2,e1)*multi(s1,e1,e2)>=0)&&
  (multi(s2,s1,e2)*multi(s2,e2,e1)>=0);
}
double dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int main()
{
int n,i;
line in;
list<line>::iterator iter1,iter2;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&in.a.x,&in.a.y,&in.b.x,&in.b.y);
in.num=i+1;
dlist.push_back(in);
}
for(iter1=dlist.begin();iter1!=dlist.end();iter1++)
for(iter2=dlist.begin();iter2!=iter1;)
{
if(is((*iter1).a,(*iter1).b,(*iter2).a,(*iter2).b))
iter2=dlist.erase(iter2);
else
iter2++;
}
printf("Top sticks: %d",(*dlist.begin()).num);
for(iter1=++dlist.begin();iter1!=dlist.end();iter1++)
printf(", %d",(*iter1).num);
printf(".\n");
dlist.clear();
}
return 0;
}
 

 

  评论这张
 
阅读(73)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018