Theo bước chân Tôi xuất bản các vấn đề từ phần Thuật toán (lập trình thể thao cổ điển. Trong một tiếng rưỡi, bạn cần giải quyết ba vấn đề bằng Java, C#, C++ hoặc Python.)
1. Bánh cho sáu người
Báo cáo sự cố
Thời gian giới hạn là 4 giây.
Bạn có một cái bánh. Khi nhìn từ trên xuống, chiếc bánh có hình đa giác lồi (đúng chuẩn). Bạn được cho tọa độ của các đỉnh theo số nguyên X và Y.
Bạn có năm người bạn. Bạn muốn chia chiếc bánh thành sáu phần có diện tích bằng nhau (nhưng không nhất thiết phải có hình dạng giống nhau). Tất nhiên, ai cũng có thể thực hiện được điều đó trong năm lần cắt, nhưng chỉ có người chuyên nghiệp mới có thể thực hiện được điều đó trong ba lần cắt.
Tìm ba đường cắt thẳng qua một điểm sẽ chia chiếc bánh thành sáu phần bằng nhau. In {x, y, d1, d2, d3}, trong đó (x, y) là điểm chung của cả ba đường cắt và d1, d2, d3 là các góc định hướng của các vết cắt tính bằng radian.
Định nghĩaLớp: CakeForSix
Phương pháp: cắt
Tham số: int[], int[] Trả về: double[] Chữ ký phương thức: double[] cut(int[] x, int[] y)
(hãy chắc chắn rằng phương pháp của bạn là công khai)
Ghi chú
- Hướng dương dọc theo trục x là 0 (radian), hướng dương dọc theo trục y là pi/2 (radian).
- Việc cắt theo hướng d tương tự như việc cắt theo hướng pi*k+d cho bất kỳ số nguyên k nào.
- Bạn có thể xuất ra bất kỳ hướng nào, chúng không nhất thiết phải từ [0, pi).
- Học sinh chấm sẽ tính diện tích sáu miếng bánh của bạn theo cách nhân đôi. Câu trả lời sẽ được chấp nhận nếu chênh lệch tương đối hoặc tuyệt đối giữa chúng nhỏ hơn 10^(-4).
- Chính xác hơn, hãy để X và Y là diện tích nhỏ nhất và lớn nhất trong sáu diện tích do học sinh tính toán. Sau đó câu trả lời của bạn sẽ được chấp nhận nếu Y
- (Phiên bản gốc của vấn đề sử dụng độ chính xác 1e-7 thay vì 1e-4. Để giải quyết vấn đề này trong kho lưu trữ, giới hạn độ chính xác đã được hạ xuống do sự hiện diện của các trường hợp gọi có khả năng khiến vấn đề không thể giải quyết được với độ chính xác của 1e-7. Trong thế giới lý tưởng, các giới hạn không cho phép những trường hợp như vậy và vẫn yêu cầu độ chính xác cao, do đó việc giải bài toán bằng một số tối ưu hóa số tổng quát là không dễ dàng.)
Hạn chế
- x chứa từ 3 đến 50 phần tử.
- y chứa cùng số phần tử như x.
- tất cả các tọa độ từ 0 đến 10
- x và y xác định một đa giác lồi theo hướng ngược chiều kim đồng hồ.
bản gốc bằng tiếng anh
Báo cáo vấn đề
Giới hạn thời gian là 4 giây.
Bạn có một cái bánh. Nhìn từ trên xuống, chiếc bánh là một hình đa giác lồi (đúng nghĩa). Bạn được cung cấp tọa độ các đỉnh của nó trong int[]sx và y.
Bạn có năm người bạn. Bây giờ bạn muốn cắt chiếc bánh thành sáu miếng có diện tích bằng nhau (nhưng không nhất thiết phải có hình dạng bằng nhau). Tất nhiên, bất cứ ai cũng có thể làm được điều đó trong năm lần cắt - nhưng chỉ một chuyên gia thực sự mới có thể làm được điều đó trong ba lần!
Tìm ba đường thẳng đi qua cùng một điểm để cắt chiếc bánh thành sáu phần có kích thước bằng nhau. Trả về {x, y, d1, d2, d3}, trong đó (x, y) là điểm chung của ba đường cắt và d1, d2, d3 là hướng của chúng tính bằng radian.
Định nghĩa
Lớp: CakeForSix
Phương pháp: cắt
Tham số: int[], int[] Trả về: double[] Chữ ký phương thức: double[] cut(int[] x, int[] y)
(hãy chắc chắn rằng phương pháp của bạn là công khai)
Chú ý
— Chiều dương dọc theo trục x là 0 (radian), chiều dương dọc theo trục y là pi/2 (radian).
— Cắt theo hướng d giống như cắt theo hướng pi*k+d với mọi số nguyên k.
— Bạn có thể quay lại bất kỳ hướng nào, không nhất thiết phải từ [0,pi).
— Giáo viên chấm sẽ tính diện tích của sáu miếng bánh của bạn theo cách nhân đôi. Câu trả lời sẽ được chấp nhận nếu chênh lệch tương đối hoặc tuyệt đối giữa chúng nhỏ hơn 10^(-4).
— Chính xác hơn, coi X và Y là diện tích nhỏ nhất và lớn nhất trong sáu diện tích của bạn, theo tính toán của học sinh. Khi đó, câu trả lời của bạn sẽ được chấp nhận nếu Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Phiên bản gốc của bài toán sử dụng độ chính xác 1e-7 thay vì 1e-4. Để giải quyết vấn đề này trong kho lưu trữ, giới hạn độ chính xác đã được hạ xuống do tồn tại các trường hợp thử thách mà rất có thể khiến bài toán không thể giải được với độ chính xác 1e-7 Trong một thế giới lý tưởng, các ràng buộc sẽ không cho phép những trường hợp như vậy và vẫn yêu cầu độ chính xác cao, do đó không dễ giải quyết vấn đề thông qua một số tối ưu hóa số chung.)
Những ràng buộc
— x sẽ có từ 3 đến 50 phần tử.
— y sẽ có cùng số phần tử như x.
— Tất cả các tọa độ sẽ nằm trong khoảng từ 0 đến 10,000.
— x và y sẽ mô tả một đa giác lồi theo thứ tự ngược chiều kim đồng hồ.
Ví dụ
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Trả về:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Một hình lục giác đối xứng nhưng không đều. Câu trả lời ví dụ tương ứng với việc cắt nó làm đôi theo chiều ngang và thực hiện hai vết cắt khác ở giữa để chia mỗi mảnh thành ba phần.
1)
{0, 1000, 0}
{0, 0, 1000}
Trả về:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Tam giác bên phải. Một lần nữa, chúng ta có thể bắt đầu bằng một trong ba vết cắt dọc theo trục đối xứng.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Trả về:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Ngũ giác không đều.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Trả về: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Một hình vuông quay được 45 độ.
[]
Chỉ những người dùng đã đăng ký mới có thể tham gia khảo sát. , xin vui lòng.
Tôi đã giải quyết vấn đề cho
-
trong vòng chưa đầy 10 phút
-
Phút 10-30
-
Phút 30-60
-
1-2 giờ
-
trong hơn 2 giờ
-
khác
42 người dùng bình chọn. 47 người dùng bỏ phiếu trắng.
Nguồn: www.habr.com