Link Sub: http://www.spoj.com/PTIT/problems/P173SUMF/
Người Gửi: Funny
- Problem:
Ngày nay có một cậu bé vì tên quá xấu nên buộc phải đổi tên thành Cơm, ngày này năm xưa – lúc Cơm đang học lớp 8, cậu được học một kiến thức mới đó là trung điểm của đoạn thẳng, hồi đó cô giáo cho Cơm 1 bài toán như sau : Cho n điểm trên mặt phẳng A[1], A[2], … A[n] với n là số lẻ. 2 điểm M[i] và M[i-1] sẽ đối xứng với nhau qua A[ (i-1) mod n] (với mọi số tự nhiên i). Hai điểm đối xứng với nhau qua điểm X khi X là trung điểm của đoạn thẳng nối 2 điểm đó. Cho M[0] và số nguyên dương j, tìm điểm M[j].Input
- Dòng đầu tiên gồm 2 số nguyên n (1 <= n <= 10^5 – n là số lẻ), và số nguyên dương j (1<= n <= 10^18) là chỉ số điểm M[j] cần tìm.
- Dòng thứ 2 chứa 2 số nguyên là tọa độ điểm M[0].
- n dòng sau mỗi dòng gồm 1 cặp số nguyên là tọa độ của điểm A[i] ( i = 1..n) có giá trị tuyệt đối không quá 1000.
Output
- Một dòng duy nhất gồm 2 số nguyên là tọa độ của điểm M[j].
Example:
- Một dòng duy nhất gồm 2 số nguyên là tọa độ của điểm M[j].
Input
3 4
0 0
1 1
2 3
-5 3
Output:
14 0
Input
3 1
5 5
1000 1000
-1000 1000
3 100
Output:
1995 1995
- Solution:
Input
3 1
5 5
1000 1000
-1000 1000
3 100
Output:
1995 1995
- Bài này đúng như tiêu đề là hình học lớp 6 thôi! Đó là (M[i]_x+M[i-1]_x)/2=A[(i-1)%n]_x; (M[i]_y+M[i-1]_y)/2=A[(i-1)%n]_y; - Nhưng nếu làm trâu thì chắc chắn sẽ quá time. -> Mình gợi ý là nó có quy luật nhé ^^! Cứ 2*n lượt thì tọa độ nó lại trở về như ban đầu :v (Không tin thì bạn cứ thử nháp mà xem :D) -> Vậy thì chỉ cần tính 2*n tọa độ đầu tiên là Ô Sờ Kê.