cf13B Letter A(分类+简单计算几何,,)
2024-10-20 20:30:31
题意:
给三个线段(每个线段的两个端点的坐标),问这三个线段能否组成字母A。
组成字母A的条件:
1.两个线段有公共端点。
2.这两个线段夹角小于等于90度。
3.第三个线段的两个端点分别在这两个线段上,且各自分割的大小比率不超过4:1
思路:
直接。。。。。
应该开始积累计算几何的代码了,,,,
代码:
struct Point{
double x,y;
};
struct segment{
Point a,b;
}
S[5]; bool samePoint(Point a,Point b){
if(fabs(a.x-b.x)<eps && fabs(a.y-b.y)<eps){
return true;
}
return false;
}
bool PointOnSegment(Point a,segment L){
if((a.x-L.a.x)*(L.b.y-L.a.y)==(a.y-L.a.y)*(L.b.x-L.a.x)
&& min(L.a.x,L.b.x)<=a.x && a.x<=max(L.a.x,L.b.x)
&& min(L.a.y,L.b.y)<=a.y && a.y<=max(L.a.y,L.b.y)){
return true;
}
return false;
}
double rates(Point a,segment L){
double l1=(a.x-L.a.x)*(a.x-L.a.x)+(a.y-L.a.y)*(a.y-L.a.y);
double l2=(a.x-L.b.x)*(a.x-L.b.x)+(a.y-L.b.y)*(a.y-L.b.y);
if(l1<eps || l2<eps){
return 999999.0;
}
if(l1<l2){
return l2/l1;
}
else{
return l1/l2;
}
}
ll Cos(double x1,double y1,double x2,double y2){
if(x1*x2+y1*y2>=0){
return true;
}
return false;
}
bool solve(){
//1 and 2
bool t1=samePoint(S[1].a,S[2].a);
bool t2=samePoint(S[1].a,S[2].b);
bool t3=samePoint(S[1].b,S[2].a);
bool t4=samePoint(S[1].b,S[2].b);
if(t1||t2||t3||t4){
bool flag=false;
if(t1){
double x1,y1,x2,y2;
x1=S[1].b.x-S[1].a.x;
y1=S[1].b.y-S[1].a.y;
x2=S[2].b.x-S[2].a.x;
y2=S[2].b.y-S[2].a.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t2){
double x1,y1,x2,y2;
x1=S[1].b.x-S[1].a.x;
y1=S[1].b.y-S[1].a.y;
x2=S[2].a.x-S[2].b.x;
y2=S[2].a.y-S[2].b.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t3){
double x1,y1,x2,y2;
x1=S[1].a.x-S[1].b.x;
y1=S[1].a.y-S[1].b.y;
x2=S[2].b.x-S[2].a.x;
y2=S[2].b.y-S[2].a.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t4){
double x1,y1,x2,y2;
x1=S[1].a.x-S[1].b.x;
y1=S[1].a.y-S[1].b.y;
x2=S[2].a.x-S[2].b.x;
y2=S[2].a.y-S[2].b.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(flag){
if(PointOnSegment(S[3].a,S[1]) && PointOnSegment(S[3].b,S[2])){
if(rates(S[3].a,S[1])<=16.0 && rates(S[3].b,S[2])<=16.0){
return true;
}
}
if(PointOnSegment(S[3].b,S[1]) && PointOnSegment(S[3].a,S[2])){
if(rates(S[3].b,S[1])<=16.0 && rates(S[3].a,S[2])<=16.0){
return true;
}
}
}
} //1 and 3
t1=samePoint(S[1].a,S[3].a);
t2=samePoint(S[1].a,S[3].b);
t3=samePoint(S[1].b,S[3].a);
t4=samePoint(S[1].b,S[3].b);
if(t1||t2||t3||t4){
bool flag=false;
if(t1){
double x1,y1,x2,y2;
x1=S[1].b.x-S[1].a.x;
y1=S[1].b.y-S[1].a.y;
x2=S[3].b.x-S[3].a.x;
y2=S[3].b.y-S[3].a.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t2){
double x1,y1,x2,y2;
x1=S[1].b.x-S[1].a.x;
y1=S[1].b.y-S[1].a.y;
x2=S[3].a.x-S[3].b.x;
y2=S[3].a.y-S[3].b.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t3){
double x1,y1,x2,y2;
x1=S[1].a.x-S[1].b.x;
y1=S[1].a.y-S[1].b.y;
x2=S[3].b.x-S[3].a.x;
y2=S[3].b.y-S[3].a.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t4){
double x1,y1,x2,y2;
x1=S[1].a.x-S[1].b.x;
y1=S[1].a.y-S[1].b.y;
x2=S[3].a.x-S[3].b.x;
y2=S[3].a.y-S[3].b.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(flag){
if(PointOnSegment(S[2].a,S[1]) && PointOnSegment(S[2].b,S[3])){
if(rates(S[2].a,S[1])<=16.0 && rates(S[2].b,S[3])<=16.0){
return true;
}
}
if(PointOnSegment(S[2].b,S[1]) && PointOnSegment(S[2].a,S[3])){
if(rates(S[2].b,S[1])<=16.0 && rates(S[2].a,S[3])<=16.0){
return true;
}
}
}
} //2 and 3
t1=samePoint(S[2].a,S[3].a);
t2=samePoint(S[2].a,S[3].b);
t3=samePoint(S[2].b,S[3].a);
t4=samePoint(S[2].b,S[3].b);
if(t1||t2||t3||t4){
bool flag=false;
if(t1){
double x1,y1,x2,y2;
x1=S[2].b.x-S[2].a.x;
y1=S[2].b.y-S[2].a.y;
x2=S[3].b.x-S[3].a.x;
y2=S[3].b.y-S[3].a.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t2){
double x1,y1,x2,y2;
x1=S[2].b.x-S[2].a.x;
y1=S[2].b.y-S[2].a.y;
x2=S[3].a.x-S[3].b.x;
y2=S[3].a.y-S[3].b.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t3){
double x1,y1,x2,y2;
x1=S[2].a.x-S[2].b.x;
y1=S[2].a.y-S[2].b.y;
x2=S[3].b.x-S[3].a.x;
y2=S[3].b.y-S[3].a.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(t4){
double x1,y1,x2,y2;
x1=S[2].a.x-S[2].b.x;
y1=S[2].a.y-S[2].b.y;
x2=S[3].a.x-S[3].b.x;
y2=S[3].a.y-S[3].b.y;
if(Cos(x1,y1,x2,y2)){
flag=true;
}
}
if(flag){
if(PointOnSegment(S[1].a,S[2]) && PointOnSegment(S[1].b,S[3])){
if(rates(S[1].a,S[2])<=16.0 && rates(S[1].b,S[3])<=16.0){
return true;
}
}
if(PointOnSegment(S[1].b,S[2]) && PointOnSegment(S[1].a,S[3])){
if(rates(S[1].b,S[2])<=16.0 && rates(S[1].a,S[3])<=16.0){
return true;
}
}
}
} return false;
} int T;
int main(){ cin>>T;
while(T--){
scanf("%lf%lf%lf%lf",&S[1].a.x,&S[1].a.y,&S[1].b.x,&S[1].b.y);
scanf("%lf%lf%lf%lf",&S[2].a.x,&S[2].a.y,&S[2].b.x,&S[2].b.y);
scanf("%lf%lf%lf%lf",&S[3].a.x,&S[3].a.y,&S[3].b.x,&S[3].b.y);
if(solve()){
puts("YES");
}else{
puts("NO");
}
} return 0;
}
最新文章
- 关于Repository、IUnitOfWork 在领域层和应用服务层之间的代码分布与实现
- Hive修改表
- new trip
- ArcGIS Runtime for Android开发教程V2.0(8)基础篇-----地图事件
- 有关UIImageView+AFNetworking 下载图片的线程问题
- 分页加查询的sql语句
- C# 将XML转换成DataSet【转】
- SQLServer2014新功能
- 第一次写博客,就写如何向外行介绍自己做的是什么,那个我是做web的
- 共60课:Python基础教程
- echarts起始角度
- 使用Spring Cache缓存出现的小失误
- Cash Machine POJ - 1276 多重背包二进制优化
- SLAM数据集整理
- Zepto的使用以及注意事项
- Visual Studio 2015+InstallShield 2015
- 转:ASP.NET MVC 多语言实现技巧 最简、最易维护和最快速开发
- jdk1.8
- Android开发–Intent-filter属性详解
- 2017-2018-1 JAVA实验站 冲刺 day04