题目大意:给定一系列线段,以及放在平面上的顺序,给出没有被其他覆盖的线段。

解题关键:线段相交的判断。

满足两个条件即可:快速排斥实验、跨立实验。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const double eps=1e-;
int sgn(double x){
if(fabs(x)<eps)return ;
else if(x<) return -;
else return ;
}
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.y-y*b.x;}
double operator*(const Point &b)const{return x*b.x+y*b.y;}
};
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){s=_s;e=_e;}
};
//判断线段相交,模板
bool inter(Line l1,Line l2){
return
max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&
max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&
max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&
max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&
sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=&&
sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=;
} const int MAXN=;
Line line[MAXN];
bool flag[MAXN];
int main(){
int n;
double x1,y1,x2,y2;
while(scanf("%d",&n),n){
for(int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[i]=Line(Point(x1,y1),Point(x2,y2));
flag[i]=true;
}
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++)
if(inter(line[i],line[j])){
flag[i]=false;
break;
}
}
printf("Top sticks: ");
bool first=true;
for(int i=;i<=n;i++)
if(flag[i]){//只是为了控制格式
if(first)first=false;
else printf(", ");
printf("%d",i);
}
printf(".\n");
} return ;
}

最新文章

  1. JavaScript异步编程的主要解决方案—对不起,我和你不在同一个频率上
  2. .Net Globalization and Localization
  3. Tomcat服务器重启失败:The server may already be running in another process, or a system process may be using the port.
  4. eclipse error pages打红X的解决方法
  5. apache 指定的网络名不再可用 原因及解决方法
  6. SQL Server安全(8/11):数据加密(Data Encryption)
  7. Scalaz(33)- Free :算式-Monadic Programming
  8. 客户端调用服务端webservice的端口问题
  9. VS 2013 未找到与约束contractname Microsoft.VisualStudio.Utilities.IContentTypeRegistryService...匹配的导出[vs故障]【转】
  10. BZOJ 2084: [Poi2010]Antisymmetry
  11. js语法
  12. IOS 开发之文件管理
  13. chrome主页被篡改为360该溶液的导航
  14. 有关conv_std_logic_vector和conv_integer
  15. hdu--1013--Digital Roots(字符串)
  16. Extensions in UWP Community Toolkit - SurfaceDialTextbox
  17. 【重学计算机】机组D6章:中央处理器
  18. 第三次scrum冲刺
  19. SDE ST_Geometry SQL st_intersects查询很慢的解决方法
  20. IIS8.5 运行WCF

热门文章

  1. IIS7配置PHP简要说明
  2. 《Advanced Bash-scripting Guide》学习(十九):两个整数的最大公约数
  3. hdu 2509 Be the Winner(anti nim)
  4. uva 1025 A Spy int the Metro
  5. Hive数据分析——Spark是一种基于rdd(弹性数据集)的内存分布式并行处理框架,比于Hadoop将大量的中间结果写入HDFS,Spark避免了中间结果的持久化
  6. 清新大气的ListView下拉上拉刷新--第三方开源--PullDownListView
  7. derby_学习_00_资源帖
  8. 11462 Age Sort(计数排序)
  9. 关于/usr/bin/ld: cannot find -lcrypto 的错误
  10. Linux 修改PostgreSQL外部访问白名单