LightOJ 1077 How Many Points?
Given two points A and B on the X-Y plane, output the number of the lattice points on the segment AB. Note that A and B are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both x and y co-ordinate as integer.
For example, for A (3, 3) and B (-1, -1) the output is 5. The points are: (-1, -1), (0, 0), (1, 1), (2, 2) and (3, 3).
Input
Input starts with an integer T (≤ 125), denoting the number of test cases.
Each case contains four integers, Ax, Ay, Bx and By. Each of them will be fit into a 32 bit signed integer.
Output
For each test case, print the case number and the number of lattice points between AB.
Sample Input
이
3 3 -1 -1
0 0 5 2
Sample Output
Case 1: 5
Case 2: 2
제목은 매우 간단하다. 바로 너로 하여금 두 개의 정수점이 연결된 선의 정수점(양쪽 끝 포함)이 몇 개인지 구하게 하는 것이다
예를 들어 (1,1)(3,3) 사이의 점에는 (1,1), (2,2), (3,3) 세 개의 점이 있다.
이 문제를 보고 나는 사율로 하려고 했는데 결국 두 시간 동안 했는데 여전히 틀렸다. 나중에야 생각이 틀렸다는 것을 알게 되었고 공약수를 구하면 나올 수 있었다.
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{
int tCase,t=1;
long long x1,y1,y2,x2;
scanf("%d",&tCase);
while(tCase--)
{
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
printf("Case %d: %lld
",t++,(long long)__gcd(abs(y2-y1),abs(x2-x1))+1);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
application ---- enter and save the file codeInput file name and content - input_content.html Receive content and save file and content - input_content01.jsp...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.