这道题我刚开始是直接求出直线交点,然后再判断是否在线段上,不知道为什么wa了。
后来看了discuss,看到有个挺好的方法:
当点A和点B在线段2的两侧,并且点C和点D在线段1的两侧时,两线段相交,否则不相交
之后一次过的,纪念下
#include<stdio.h>
#include<math.h>
#define eps 1e-9
struct segment
{
double a,c,b;
double x1,x2,y1,y2;
}f[105];
void calcu(double x1,double y1,double x2,double y2,int s)//求出直线ax+by+c=0
{
segment p;
if(fabs(x1-x2)<eps)
{
p.a=0;p.b=1;p.c=-x1;
}
else if(fabs(y1-y2)<eps)
{
p.a=1;p.b=0;p.c=-y1;
}
else
{
p.a=1;p.b=(x2-x1)/(y1-y2);p.c=-x1-p.b*y1;
}
p.x1=x1;p.x2=x2;
p.y1=y1;p.y2=y2;
f[s]=p;
}
double online(segment l,double x,double y)
{
return l.a*x+l.b*y+l.c;
}
bool judge(segment l1,segment l2)
{
if(online(l1,l2.x1,l2.y1)*online(l1,l2.x2,l2.y2)>0)//判断是否在同一侧,注意,有一个端点在线段上也算是在不同侧
return 0;
if(online(l2,l1.x1,l1.y1)*online(l2,l1.x2,l1.y2)>0)
return 0;
return 1;
}
int main()
{
int i,j,k,n;
double x1,x2,y1,y2;
while(scanf("%d",&n)!=-1&&n)
{
for(i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
calcu(x1,y1,x2,y2,i);
}
int ans=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(judge(f[i],f[j]))
ans++;
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
acm hdu as easy as a+b
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...
HDU 1022 Train Problem I 附详细思路
The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number ...
A simple SDK for HDU. hdu-api 是一个集结 HDU 所有教务管理服务的 SDK,提供了一卡通服务、考试、课表、选课和一些公共信息如空闲教室、上课时间等信息的 API。 hdu-api 主要基于 Requests 库和 Beautiful Soup 库...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?n)⊕n,...
考试类精品--A simple SDK for HDU. 一个提供一卡通服务、考试、课表、选课和公共信息等 API
acm经典题、结题报告,对初学者非常用用,我就从中学到了很多东西
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu_2102_passed_sorce
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电hdu acm资料所用杭电的acm题
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
#include using namespace std; int main(){ char a[2]; while(cin>>a){ int temp; for(int i=0;... if(a[i]>a[i+1]) ... temp=a[i];... a[i]=a[i+1];... cout<<a[0]<<" "<<a[1]<<" "<<a[2]; } return 0; }
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.