#include<stdio.h>
#include<math.h> const double eps=1e-8;
int n;
int cmp(double x)
{ if(fabs(x)<=eps)return 0;
if(x<0)return -1;
return 1;
} struct Point
{
double x,y;
Point (){}
Point (double _x,double _y)
{
x=_x;
y=_y;
}
Point operator -(const Point &b)const {
return Point (x-b.x,y-b.y);
}
double operator *(const Point &b)const {
return x*b.x+y*b.y;
}
double operator ^(const Point &b)const{
return x*b.y-b.x*y;
}
}; struct Line
{
Point s,e;
Line (){}
Line (Point _s,Point _e)
{
s=_s;
e=_e;
}
}; Line line [(int)1e5+5];
double xmult(Point p0,Point p1,Point p2)
{
return (p1-p0)^(p2-p0);
} bool seg_seg(Line l1,Line l2)
{
return cmp(xmult(l1.s,l2.s,l2.e))*cmp(xmult(l1.e,l2.s,l2.e))<=0&&cmp(xmult(l2.e,l1.s,l1.e))*cmp(xmult(l2.s,l1.s,l1.e))<=0;
} bool check(int num)
{
for(int j=num+1;j<n;j++)
{
if(seg_seg(line[num],line[j])==true)
return false;
}
return true;
} int a[1005];
int main()
{
double x1,x2,y1,y2;
while(scanf("%d",&n),n)
{
int t=0;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[i]=Line(Point(x1,y1),Point(x2,y2));
}
for(int i=0;i<n;i++)
if(check(i))
a[t++]=i;
printf("Top sticks: ");
for(int i=0;i<t;i++)
{
printf("%d",a[i]+1);
if(i<t-1)
printf(", "); }
printf(".\n");
}
}

思路:TOP STICK :压在最上边的木棍,从最先放的木棍开始遍历,如果在其后边的木棍不压在它身上,即其后的木棍不与其相交(线段相交),则这个木棍就是top stick

最新文章

  1. java中的移位运算符:&lt;&lt;,&gt;&gt;,&gt;&gt;&gt;总结
  2. 基于SpringMVC的增删改查
  3. mui禁止滚动条和禁止滚动
  4. _mysql.c(42) : fatal error C1083: Cannot open include file: &#39;config-win.h&#39;:问题的解决 mysql安装python
  5. [Linux] CentOS 加入开机启动
  6. phalcon: acl权限控制
  7. 身为java程序员你需要知道的网站(包含书籍,面试题,架构...)
  8. 内容高度小于窗口高度时版权div固定在底部
  9. 2)PHP中把读取.txt中内容并转为UTF-8格式
  10. cygwin 下安装python MySQLdb
  11. Java成神之路技术整理(长期更新)
  12. TSP(Traveling Salesman Problem)-----浅谈旅行商问题(动态规划,回溯实现)
  13. Jenkins 配置邮件通知步骤
  14. Python Day 12
  15. es6 set
  16. 配置iis支持json解析,配置ssi
  17. nmap简单使用
  18. 仿sql注入 sql
  19. bootstrap-treeview使用
  20. 阿里云收集服务器性能指标的python脚本

热门文章

  1. 【SpringBoot1.x】SpringBoot1.x 检索
  2. LeetCode747 至少是其他数字两倍的最大数
  3. windows打包脚本出现 /bin/sh^M: 坏的解释器: 没有那个文件或目录 错误
  4. Desired_Capabilities配置
  5. 【Oracle】重命名表空间
  6. leetcode 470. 用 Rand7() 实现 Rand10() (数学,优化策略)
  7. 1V升5V芯片,1V升5V电路图规格书
  8. 【源码解读】js原生消息提示插件
  9. 【JeecgBoot】关于 jeecg-boot 的项目理解、使用心得和改进建议
  10. 配接Cisco设备