(叉积,线段判交)HDU1086 You can Solve a Geometry Problem too
2024-10-15 10:17:06
You can Solve a Geometry Problem too
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12959 Accepted Submission(s): 6373
Problem Description
Many geometry(几何)problems were designed in the ACM/ICPC. And now, I also prepare a geometry problem for this final exam. According to the experience of many ACMers, geometry problems are always much trouble, but this problem is very easy, after all we are now attending an exam, not a contest :)
Give you N (1<=N<=100) segments(线段), please output the number of all intersections(交点). You should count repeatedly if M (M>2) segments intersect at the same point.
Give you N (1<=N<=100) segments(线段), please output the number of all intersections(交点). You should count repeatedly if M (M>2) segments intersect at the same point.
Note:
You can assume that two segments would not intersect at more than one point.
Input
Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s ending.
A test case starting with 0 terminates the input and this test case is not to be processed.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output
For each case, print the number of intersections, and one line one case.
Sample Input
2
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.00
3
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.000
0.00 0.00 1.00 0.00
0
Sample Output
1
3
叉积求线段判交的参考链接:
https://www.cnblogs.com/Duahanlang/archive/2013/05/11/3073434.html
https://www.cnblogs.com/tuyang1129/p/9390376.html
C++代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Point{
double x1,y1,x2,y2;
}node[];
int cross(const Point &a, const Point &b){
double k1 = (a.x2 - a.x1) * (b.y1 - a.y1) - (a.y2 - a.y1) * (b.x1 - a.x1);
double k2 = (a.x2 - a.x1) * (b.y2 - a.y1) - (a.y2 - a.y1) * (b.x2 - a.x1);
if(k1 * k2 <= ){
return ;
}
else
return ;
}
int main(){
int n;
while(scanf("%d",&n),n){
int ans = ;
for(int i = ; i < n; i++){
scanf("%lf%lf%lf%lf",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);
}
for(int i = ; i < n-; i++){
for(int j = i + ; j < n; j++){
ans += (cross(node[i],node[j])) && (cross(node[j],node[i]));
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- [ACM_其他] Modular Inverse [a关于模m的逆 模线性方程]
- Android 使用dagger2进行依赖注入(基础篇)
- ArcGIS 坐标系统文件
- Bash判断文件夹(目录)是否存在
- Java String.format 自动补全不够的位数
- CF-Approximating a Constant Range
- 关于div+css布局值得注意的地方
- ci框架中输出sql语句
- hyper-v 安装Centos及网络配置
- cadence焊盘及元件封装制作
- EF 简单介绍<;一>;
- android ButterKnife 点击事件没反应的解决方案
- 生成条形码插件 条形码--JsBarcode
- 转帖--计算机网络基础知识大总汇 https://www.jianshu.com/p/674fb7ec1e2c?utm_campaign=maleskine&;utm_content=note&;utm_medium=seo_notes&;utm_source=recommendation
- 索引视图DEMO1
- C++中四种类型转换方式(ynamic_cast,const_cast,static_cast,reinterpret_cast)
- Struts2:No result defined for action com.yibai.user.action.LoginAction and result input
- mysql恢复备份错误:Got a packet bigger than &#39;max_allowed_packet&#39; bytes
- 看图说说JVM GC收集算法
- 1111: [POI2007]四进制的天平Wag