题目大意:

给定n条线段的端点

依次放上n条线段 判断最后在最上面(不被覆盖)的线段有哪些

到当前线段后 直接与之前保存的未被覆盖的线段判断是否相交就可以了

#include <cstdio>
#include <algorithm>
#include <string.h>
#include <set>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std; const double eps=1e-;
double add(double a,double b) {
if(abs(a+b)<eps*(abs(a)+abs(b))) return ;
return a+b;
}
struct P {
double x,y;
P(){};
P(double _x,double _y):x(_x),y(_y){}
P operator - (P p) { return P(add(x,-p.x),add(y,-p.y)); }
P operator + (P p) { return P(add(x,p.x),add(y,p.y)); }
P operator * (double d) { return P(x*d,y*d); }
bool operator == (P p) { return x==p.x && y==p.y; }
bool operator < (P p) {
if(x==p.x) return y<p.y;
return x<p.x;
}
double dot(P p) { return add(x*p.x,y*p.y); }
double det(P p) { return add(x*p.y,-y*p.x); }
}p[];
int n;
set <int> s;
bool vis[]; P ins(P a,P b,P c,P d) {
return a+(b-a)*((c-d).det(d-a)/(c-d).det(b-a));
}
bool onSeg(P a,P b,P c) {
return (a-c).det(b-c)== && (a-c).dot(b-c)<=;
}
bool insSS(P a,P b,P c,P d)
{
if((a-b).det(c-d)==) {
return onSeg(a,b,c) || onSeg(a,b,d)
|| onSeg(c,d,a) || onSeg(c,d,b);
}
else {
P r=ins(a,b,c,d);
return onSeg(a,b,r) && onSeg(c,d,r);
}
} int main()
{
while(~scanf("%d",&n)) {
if(n==) break;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(insSS(p[i],p[i+n],p[j],p[j+n])) {
vis[i]=; break;
}
bool yes=;
printf("Top sticks:");
for(int i=;i<=n;i++) {
if(vis[i]) continue;
if(yes) printf(", %d",i);
else yes=, printf(" %d",i);
}
printf(".\n");
} return ;
}

这篇的注释里有直线交点的推导

最新文章

  1. java数组
  2. Spark MLlib Data Type
  3. C++字符串处理封装类String
  4. [转] Manacher算法详解
  5. qt 4.6.2 vs 2005 + QCreator 开发环境配置(有注册码)
  6. QNX系统-关于delay函数与sleep函数的区别
  7. 新秀nginx源代码分析数据结构篇(两) 双链表ngx_queue_t
  8. 每个程序员都应该学习使用Python或Ruby
  9. 使用swagger管理接口
  10. Java工程师必备书单
  11. admui框架使用经验
  12. iOS 出现内存泄漏的几种原因
  13. 服务容错和Hystrix
  14. Vector 是线程安全的,是不是在多线程下操作Vector就可以不用加Synchronized
  15. vue组件通信之任意级组件之间的通信
  16. Fiddler(三)Fiddler 报错creation of the root certificate was not successful
  17. vue之给a标签赋值
  18. JAVA的关键特性
  19. LoadRunner参数化取值与连接数据库
  20. malloc/free 与 new/delete 比较

热门文章

  1. Web API 接口参考
  2. Delphi 日期函数(Day、Mon、Year、Week)使用方法描述
  3. 后缀自动机求多串LCS——spojlcs2
  4. 大转盘抽奖css3+js(简单书写)
  5. NX二次开发-UFUN添加工程图投影视图UF_DRAW_add_orthographic_view
  6. Java-Class-C:org.springframework.http.HttpEntity
  7. 3.7.4 Tri0 and tri1 nets
  8. [17]APUE:线程
  9. 4.1_springboot2.2任务之异步、定时、邮件任务
  10. Reading books /// Prim+BFS oj21633