网站功能定制合同,网站资料上传教程,wordpress电子书下载地址,淄博高端网站建设乐达标题#xff1a;螺旋折线
如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)#xff0c;我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。 例如dis(0, 1)3, dis(-2, -1)9 给出整点坐标(X, Y)#xff0c;你能计算出dis(X, Y)…标题螺旋折线
如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。 例如dis(0, 1)3, dis(-2, -1)9 给出整点坐标(X, Y)你能计算出dis(X, Y)吗
【输入格式】 X和Y 对于40%的数据-1000 X, Y 1000 对于70%的数据-100000 X Y 100000 对于100%的数据, -1000000000 X, Y 1000000000 【输出格式】 输出dis(X, Y)
【输入样例】 0 1 【输出样例】 3
资源约定 峰值内存消耗含虚拟机 256M CPU消耗 1000ms 请严格按要求输出不要画蛇添足地打印类似“请您输入…” 的多余内容。 所有代码放在同一个源文件中调试通过后拷贝提交该源码。 不要使用package语句。不要使用jdk1.7及以上版本的特性。 主类的名字必须是Main否则按无效代码处理。
解析按象限划分四个部分以拐点为突破口。比赛的时候想到了但是一紧张就没有静下心来好好分析罪过罪过。 根据给定坐标求解拐点是比较简单的我们对于每个点都求出它x和y中较大的那个值然后我们可以得到 第一象限的拐点坐标——dx max(abs(x), abs(y))dy dx 第二象限的拐点坐标——dx -max(abs(x), abs(y))dy -dx 第三象限的拐点坐标——dx -max(abs(x), abs(y))dy dx - 1 第四象限的拐点坐标——dx max(abs(x), abs(y))dy -dx
假定拐点坐标为(dx, dy),我们有 第一象限的拐点的dfs()——(abs(dx)abs(dy))^2 第二象限的拐点的dfs()——(abs(dx)abs(dy)) * (abs(dx)abs(dy) - 1) 第三象限的拐点的dfs()——(abs(dx)abs(dy))^2 第四象限的拐点的dfs()——(abs(dx)abs(dy)) * (abs(dx)abs(dy) 1)
之后根据给定坐标(x, y)与拐点坐标(dx, dy)的关系就可以轻松的解出来了。 还要特别注意给定坐标中x或y等于0的情况这里我把四种情况分别归到了四个象限中
这样求解这个问题最后时间复杂度为O(1)
import java.util.Scanner;public class Main {static int x, y;static int df 0;public static void main(String[] args) {Scanner in new Scanner(System.in);x in.nextInt();y in.nextInt();if (x 0 y 0) {int dx Math.max(x, y);int dy dx;df (dx dy) * (dx dy);if (x dx) {df - (dx - x);}if (y dy) {df (dy - y);}} else if (x 0 y 0) {int dx Math.max(Math.abs(x), Math.abs(y));int dy -dx;df (dx Math.abs(dy)) * (dx Math.abs(dy) 1);if (x dx) {df (dx - x);}if (y dy) {df - (y - dy);}} else if (x 0 y 0) {int dx -Math.max(Math.abs(x), Math.abs(y));int dy dx 1;df (Math.abs(dx) Math.abs(dy)) * (Math.abs(dx) Math.abs(dy));if (x dx) {df - (x - dx);}if (y dy) {df (y - dy);}} else if (x 0 y 0) {int dx -Math.max(Math.abs(x), Math.abs(y));int dy -dx;df (Math.abs(dx) Math.abs(dy)) * (Math.abs(dx) Math.abs(dy) - 1);if (x dx) {df (x - dx);}if (y dy) {df - (y - dy);}}System.out.println(df);}
}
