Codeforces 123 B Squares
【摘要】 题目链接~~>
做题感悟：昨天做的这道题，做了很久找到了一点规律，但是没A掉，看了一下官方题解果断看不懂，于是乎又开始研究题目，终于历时半天把“ 她 ”搞定了，但是官方题解还是没看懂，有看懂的大神求讲解。
解题思路：
先来一张图片（貌似有点大！）
&n...
做题感悟：昨天做的这道题，做了很久找到了一点规律，但是没A掉，看了一下官方题解果断看不懂，于是乎又开始研究题目，终于历时半天把“ 她 ”搞定了，但是官方题解还是没看懂，有看懂的大神求讲解。
解题思路：
先来一张图片（貌似有点大！）
如果你画一下你会发现会是这样子的图，那么从一点走到另一点才是最少的呢 ？当然是走两者的交点，正如图中画的那样，因为如果你走交点，你可以越过两条直线， 那么这个交点数怎样算呢 ？就是途中红线和绿线经过途中蓝线的条数的最大值。
好了，现在主要求图中红线和蓝线经过的直线条数（取最大值即可），因为红线是 45度且知道一个点，so~> 我们可以知道这条直线的方称，同理我们也可以知道绿线的直线方程，这样我们就可以求出两条直线的交点了，知道交点后求经过的直线条数就简单了，但是如果你直接用交点到某个点的距离除以宽度的话，这样是不行的，因为有可能少加 1 ，或者多加 1 ，so ~> 我们可以以一条直线为标准，这里已红线为例子讲解 ( 绿线同理 ) ：我们以 135 度的橙色直线为标准，如果两点分别在橙色线两侧个数就等于两点到橙色线的距离取整 + 1 ，否则两点到橙色线的距离相减的绝对值即为经过的直线的条数。
代码：
-
#include<iostream>
-
#include<sstream>
-
#include<map>
-
#include<cmath>
-
#include<fstream>
-
#include<queue>
-
#include<vector>
-
#include<sstream>
-
#include<cstring>
-
#include<cstdio>
-
#include<stack>
-
#include<bitset>
-
#include<ctime>
-
#include<string>
-
#include<cctype>
-
#include<iomanip>
-
#include<algorithm>
-
using namespace std ;
-
#define INT __int64
-
const int INF = 0x3f3f3f ;
-
const double esp = 0.0000000001 ;
-
const double PI = acos(-1.0) ;
-
const int mod = 1000000007 ;
-
const INT Up = 1000000000 ;
-
const INT Dn = -1000000000 ;
-
const int MY = 205 ;
-
const int MX = 205 ;
-
int workA(double x1 ,double y1 ,double x2 ,double y2 ,double d)
-
{
-
double dA ,dB ;
-
int num1 ,num2 ;
-
dA = fabs(y1 + x1)/sqrt(2.0) ;
-
dB = fabs(y2 + x2)/sqrt(2.0) ;
-
num1 = (int)(dA/d + 1.0) ;
-
num2 = (int)(dB/d + 1.0) ;
-
if(((x1+y1 > 0)&&(x2 + y2 > 0)) || (x1 + y1 < 0 && x2 + y2 < 0)) // 同在一侧
-
return abs(num1 - num2) ;
-
else
-
return abs(num1 + num2 - 1) ;
-
}
-
int workB(double x1 ,double y1 ,double x2 ,double y2 ,double d)
-
{
-
double dA ,dB ;
-
int num1 ,num2 ;
-
dA = fabs(y1 - x1)/sqrt(2.0) ;
-
dB = fabs(y2 - x2)/sqrt(2.0) ;
-
num1 = (int)(dA/d) + 1 ;
-
num2 = (int)(dB/d) + 1 ;
-
if(((y1 > x1)&&(y2 > x2)) || ((y1 < x1)&&(y2 < x2))) // 如果同时大于 同时小于
-
return abs(num1 - num2) ;
-
else
-
return abs(num1 + num2 - 1) ;
-
}
-
int main()
-
{
-
double a ,b ,x1 ,y1 ,x2 ,y2 ,b1 ,b2 ,x ,y ;
-
while(~scanf("%lf%lf%lf%lf%lf%lf" ,&a ,&b ,&x1 ,&y1 ,&x2 ,&y2))
-
{
-
if(x1 != x2 && y1-y2 == x1 - x2) // 为 45 度
-
cout<<workA(x1 ,y1 ,x2 ,y2 ,sqrt(2.0)*a)<<endl ;
-
else if(x1 != x2 && y1 - y2 == x2 - x1) // 为 135 度
-
cout<<workB(x1 ,y1 ,x2 ,y2 ,sqrt(2.0)*b)<<endl ;
-
else
-
{
-
b1 = y1 - x1 ;
-
b2 = y2 + x2 ;
-
x = (b2 - b1)/2.0 ; // 交点
-
y = x + b1 ;
-
cout<<max(workA(x1 ,y1 ,x ,y ,sqrt(2.0)*a) ,workB(x2 ,y2 ,x ,y ,sqrt(2.0)*b))<<endl ;
-
}
-
}
-
return 0 ;
-
}
-
再附上官方题解：
官方代码：
-
#include <cstdio>
-
#include <algorithm>
-
#include <iostream>
-
using namespace std;
-
int a, b, x1, y1, x2, y2;
-
int x, y;
-
int main()
-
{
-
#ifndef ONLINE_JUDGE
-
freopen("in", "r", stdin);
-
freopen("out", "w", stdout);
-
#endif
-
cin >> a >> b >> x1 >> y1 >> x2 >> y2;
-
x = x1; y = y1;
-
x1 = x + y;
-
y1 = y - x;
-
-
x = x2; y = y2;
-
x2 = x + y;
-
y2 = y - x;
-
-
a *= 2;
-
b *= 2;
-
-
x1 = x1 / a + (x1 > 0);
-
x2 = x2 / a + (x2 > 0);
-
y1 = y1 / b + (y1 > 0);
-
y2 = y2 / b + (y2 > 0);
-
-
cout << max(abs(y2 - y1), abs(x2 - x1)) << endl;
-
return 0;
-
}
-
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/39927781
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）