Codeforces Round #284 (Div. 2) C题(计算几何)解题报告

时间:2023-02-10 20:35:35

题目地址

简要题意:

  给出两个点的坐标,以及一些一般直线方程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 }