HDU 1147 /// 判断两线段相交
2024-09-06 07:24:04
题目大意:
给定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 ;
}
最新文章
- java数组
- Spark MLlib Data Type
- C++字符串处理封装类String
- [转] Manacher算法详解
- qt 4.6.2 vs 2005 + QCreator 开发环境配置(有注册码)
- QNX系统-关于delay函数与sleep函数的区别
- 新秀nginx源代码分析数据结构篇(两) 双链表ngx_queue_t
- 每个程序员都应该学习使用Python或Ruby
- 使用swagger管理接口
- Java工程师必备书单
- admui框架使用经验
- iOS 出现内存泄漏的几种原因
- 服务容错和Hystrix
- Vector 是线程安全的,是不是在多线程下操作Vector就可以不用加Synchronized
- vue组件通信之任意级组件之间的通信
- Fiddler(三)Fiddler 报错creation of the root certificate was not successful
- vue之给a标签赋值
- JAVA的关键特性
- LoadRunner参数化取值与连接数据库
- malloc/free 与 new/delete 比较
热门文章
- Web API 接口参考
- Delphi 日期函数(Day、Mon、Year、Week)使用方法描述
- 后缀自动机求多串LCS——spojlcs2
- 大转盘抽奖css3+js(简单书写)
- NX二次开发-UFUN添加工程图投影视图UF_DRAW_add_orthographic_view
- Java-Class-C:org.springframework.http.HttpEntity
- 3.7.4 Tri0 and tri1 nets
- [17]APUE:线程
- 4.1_springboot2.2任务之异步、定时、邮件任务
- Reading books /// Prim+BFS oj21633