Chủ Nhật, 31 tháng 3, 2019

Bài C - Codeforces Beta Round #1

Bài C:
Đề bài:
  Ngày nay tất cả các rạp xiếc ở Berland đều có một đấu trường với đường kính 13 mét, nhưng trong mọi thứ thì khác.
  Trong các đấu trường Berland cổ đại trong các rạp xiếc được định hình là một đa giác (tam giác) đều, kích thước và số lượng góc có thể thay đổi tử rạp xiếc này đến rạp xiếc khác. Ở mỗi góc của đấu trường có một cây cột đặc biệt, và sợi dây được căng giữa các cây cột đánh dấu các cạnh của đấu trường.
  Gần đây, các nhà khoa học từ Berland đã phát hiện ra phần còn lại của đấu trường xiếc cổ đại. Họ chỉ tìm thấy ba cây cột, những cái khác đã bị thời gian pháy hủy.
  Bạn được cho các tọa độ của ba cây trụ. Tìm ra giá trị nhỏ nhất của đấu trường có thể.
Đầu vào:
+ Đầu vào gồm 3 dòng, mỗi dòng là một cặp số - tọa độ của các cột. Bất kì tọa độ nào cũng không quá 1000 by absolute value, và được cho nhiều nhất 6 chữ số sau hàng thập phân.
Đầu ra:
+ In ra diện tích nhỏ nhất có thể của đầu trường cổ. Con số này chính xác tới ít nhất 6 số phần thập phân.
Ví dụ:
Đầu vào:
0.000000 0.000000
1.000000 1.000000
0.000000 1.000000
Đầu ra:
1.00000000
Hướng dẫn:
 Các điểm có thể là các đỉnh của N- đa giác đều khi và chỉ khi với mỗi cặp, sự khác biệt của các góc cực của chúng (khi nhìn từ tâm đa giác) của 2*pi/N. Tất cả các điểm nằm trên đường tròn với cùng tâm với đa giác. Chúng ta có thể xác định vị trí trung tâm của đa giác / vòng tròn [nhưng chúng ta có thể tránh điều này, vì một hợp âm như giả sử, (x(1),y(1))-(x(2),y(2))] được nhìn thấy ở góc lớn hơn gấp đôi so với tâm điểm khác của một điểm khác của đường tròn (x(3),y(3))]
 Có nhiều cách để xác định vị trí trung tâm của vòng tròn, cách tôi đã xây dựng là xây dựng trung điểm vuông góc với các phân đoạn (x1,y1)-(x2,y2) và (x2,y2)-(x3,y3) ở dạng y=a*x+b và tìm giao điểm của chúng. Công thức y=a*x+b có nhược điểm là không thể sử dụng nếu đường thẳng song song với y, cách giải quyết có thể là xoay tất cả các điểm theo góc ngẫu nhiên (sử dụng công thức xl=x*cos(a)-y*sin(a),y'=y*cos(a)+x*sin(a)) cho đến khi không có đoạn nào nằm ngang (và do đó không có đường vuông góc nào là dọc).
  Sau khi biết tọa độ của tâm, chúng ta sử dụng hàm ưa thích: , trả về góc trong phần tư phải: a[i]=atan2(y[i]-ycenter,x[i]-xcenter) atan2.
  Diện tích của đa giác đều tăng khi tăng N, do đó có thể chỉ cần lặp qua tất cả các giá trị có thể có trên N theo thứ tự tăng dần và thoát khỏi chu kỳ khi tìm thấy N thỏa mãn đầu tiên.
 Sử dụng sin(x) là làm cho nó dễ dàng: sin(x)=0 khi x là bội của pi. Vì vậy, đối với các điểm thuộc về đa giác N, đa giác N đều.
sin(N*(a[i]-a[j])/2)=0.
 Bởi vì số học chính xác hữu hạn, fabs(sin(N*(a[i]-a[j])/2)).
Lời giải:
#include<cstdio>
#include<cmath>
#define D double
#define S(x) ((x)*(x))
#define G(t) a[t]=x[t]-x[2];b[t]=y[t]-y[2];c[t]=(S(x[t])+S(y[t])-S(x[2])-S(y[2]))/2;
#define M(p,q) (p[0]*q[1]-p[1]*q[0])
D g(D a,D b){return fabs(b)<1e-4?a:g(b,fmod(a,b));}
D x[3],y[3],a[3],b[2],c[2],A,X,Y;
int main()
{
for(int i=0;i<3;++i)scanf("%lf%lf",x+i,y+i);
G(0);G(1);
X=M(c,b)/M(a,b);
Y=M(a,c)/M(a,b);
for(int i=0;i<3;++i)a[i]=atan2(x[i]-=X,y[i]-=Y);
A=g(M_PI*2,g(fabs(a[1]-a[0]),fabs(a[2]-a[0])));
printf("%lf\n",(S(x[0])+S(y[0]))*sin(A)*M_PI/A);
}

Không có nhận xét nào:

Đăng nhận xét

Bài G - Educatioal Round 62

Đề bài: Bạn được cho 1 đồ thị vô hướng đặc biệt. Nó bao gồm $2n$ đỉnh được đánh số từ 1 đến 2n. Dưới đây là một số đặc tính của đồ thị: + ...