简要题意:
给出两个点的坐标,以及一些一般直线方程Ax+B+C=0的A、B、C,这些直线作为街道,求从一点走到另一点需要跨越的街道数。(两点都不在街道上)
思路分析:
从一点到另一点必须要跨的街道等价于两点一点在这条直线一侧,另一条在另一侧。只需要将两点坐标带进去,一正一负即可。将这些直线依次检验,统计总和。
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 int main() 7 { 8 ll x1,x2,y1,y2,n,a,b,c,s,q,ans=0; 9 scanf("%I64d%I64d",&x1,&y1); 10 scanf("%I64d%I64d",&x2,&y2); 11 scanf("%I64d",&n); 12 while(n--) 13 { 14 scanf("%I64d%I64d%I64d",&a,&b,&c); 15 s=a*x1+b*y1+c; 16 q=a*x2+b*y2+c; 17 if((s>0&&q<0)||(s<0&&q>0)) 18 ans++; 19 } 20 printf("%I64d\n",ans); 21 return 0; 22 }