Boundary（2020多校第二場(chǎng)B）

文章目錄

• • 題意：
  • 題解：
  • • 思路1：
    • • 代碼：
    • 思路二
    • • 代碼

題意：

坐標(biāo)平面有n個(gè)點(diǎn)（不與原點(diǎn)（0,0）重復(fù)）,現(xiàn)考慮一個(gè)圓，（0,0）點(diǎn)在圓的邊界，問(wèn)這個(gè)圓的邊界上最多能有多少其他的點(diǎn)（不含原點(diǎn)）？
我們看一下樣例：

4 1 1 0 2 2 0 2 2

如圖所示，我們選（0,2）為P,線(xiàn)段op對(duì)應(yīng)的角中，∠PA₂O=∠OA₃P，說(shuō)明A2，A3也在圓上，再加上p點(diǎn)，一共是三個(gè)，答案就是三

題解：

我一開(kāi)始是暴力求解，直接枚舉兩個(gè)點(diǎn)，再枚舉其他點(diǎn)看在不在邊界上，復(fù)雜度是O(n³),但顯然不行

思路1：

原點(diǎn)肯定在邊界，我們可以先枚舉一個(gè)點(diǎn)p，原點(diǎn)O與p組成線(xiàn)段op，op是圓上的一個(gè)弦，再枚舉其他點(diǎn)A，根據(jù)“同弧所對(duì)的圓周角相等”，我們計(jì)算出∠OAP，然后找到最多數(shù)（眾數(shù)）即可。但是度數(shù)相同不一定在同一個(gè)圓上（如圖），會(huì)關(guān)于OP對(duì)稱(chēng)，我們只需規(guī)定A只能在OP下方，這樣就確定位置，即OP（向量） * OA(向量) < 0
時(shí)間復(fù)雜度O（n²log n）

代碼：

#include <cstdio> #include <algorithm> using namespace std; typedef long long LL; typedef __int128_t LLL; #define N 2000 + 5int n, ans = 1, X[N], Y[N];struct Frac {LL fz, fm;Frac() : Frac(0, 1){}Frac(LL fz, LL fm) : fz(fz), fm(fm) {}bool operator < (const Frac &rhs){return (LLL) fz * rhs.fm < (LLL) fm * rhs.fz;//判斷誰(shuí)的角大 }bool operator == (const Frac &rhs)//判斷角是否相等 {return (LLL) fz * rhs.fm == (LLL) fm * rhs.fz;} }A[N];int Cross(int lhs, int rhs)//判斷是否平行 {return X[lhs] * Y[rhs] - X[rhs] * Y[lhs]; }int Dis2(int lhs, int rhs)//兩點(diǎn)的距離的平方和 {int dx = X[lhs] - X[rhs], dy = Y[lhs] - Y[rhs];return dx * dx + dy * dy; }int Sgn(int x)//用以調(diào)整x的正負(fù) {if (x > 0) return 1;if (x < 0) return -1;return 0; }Frac GetCosAngle2(int i, int j) {int a2 = Dis2(0, i);//求邊 int b2 = Dis2(i, j);int c2 = Dis2(0, j);int sgn = Sgn(b2 + c2 - a2);return Frac(1LL * sgn * (b2 + c2 - a2) * (b2 + c2 - a2), 4LL * b2 * c2);//賦值 //余弦定理 cosA=(b2+c2-a2)/2bc }int main() {scanf("%d", &n);for (int i = 1; i <= n; i ++)scanf("%d%d", X + i, Y + i);for (int i = 1; i <= n; i ++){int cnt = 0;for (int j = 1; j <= n; j ++)if (Cross(i, j) > 0)A[++ cnt] = GetCosAngle2(i, j);sort(A + 1, A + cnt + 1);for (int l = 1, r; l <= cnt; l = r){for (r = l; A[l] == A[r] && r <= cnt; r ++) ;ans = max(ans, r - l + 1);}}printf("%d\n", ans);return 0; }

思路二

任意兩個(gè)線(xiàn)段的中垂線(xiàn)的交點(diǎn)作圓心，圓肯定過(guò)兩個(gè)線(xiàn)段的四個(gè)點(diǎn)，又因?yàn)楸剡^(guò)原點(diǎn)，所以枚舉每一個(gè)點(diǎn)，求它與原點(diǎn)所做線(xiàn)段的中垂線(xiàn)，然后求中垂線(xiàn)的所有交點(diǎn)，記錄交點(diǎn)數(shù)
也就是求每個(gè)三角形的外心
特判中垂線(xiàn)都平行的情況
具體求外心的方法：
a(x1,y1) b(x2,y2) c(x3,y3)
外心o（x,y）
外心是垂直平分線(xiàn)的交點(diǎn)，也就是外心到各點(diǎn)距離相等
(x1-x) * (x1-x)-(y1-y) * (y1-y)=(x2-x) * (x2-x)+(y2-y) * (y2-y);
(x2-x) * (x2-x)+(y2-y) * (y2-y)=(x3-x) * (x3-x)+(y3-y) * (y3-y);
化簡(jiǎn)：
2*(x2-x1)x+2(y2-y1)y=x2²+y2²-x1²-y1²;
2*(x3-x2)x+2(y3-y2)y=x3²+y3²-x2²-y2²;
A1=2*(x2-x1)；
B1=2*(y2-y1)；
C1=x2²+y2²-x1²-y1²;
A2=2*(x3-x2)；
B2=2*(y3-y2)；
C2=x3²+y3²-x2²-y2²;
所以
A1x+B1y=C1;
A2x+B2y=C2;
結(jié)論：
x=((C1B2)-(C2B1))/((A1B2)-(A2B1))；
y=((A1C2)-(A2C1))/((A1B2)-(A2B1))；

代碼

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+5; const ll mod=998244353; double eqs=1e-6; struct Point{double x,y;Point(){}Point(double xx,double yy){x=xx;y=yy;} }e[maxn]; Point operator+(Point a,Point b){ //向量加return Point(a.x+b.x,a.y+b.y); } Point operator-(Point a,Point b){ //向量減return Point(a.x-b.x,a.y-b.y); } double sqr(double x){return x*x; } double dis(Point a,Point b){ //求ab的長(zhǎng)度return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } Point Circum(Point a,Point b,Point c){ //三角形外心double x1=a.x,y1=a.y;double x2=b.x,y2=b.y;double x3=c.x,y3=c.y;double a1=2*(x2-x1);double b1=2*(y2-y1);double c1=x2*x2+y2*y2-x1*x1-y1*y1;// double a2=2*(x3-x2);double b2=2*(y3-y2);double c2=x3*x3+y3*y3-x2*x2-y2*y2;double x=(c1*b2-c2*b1)/(a1*b2-a2*b1);double y=(a1*c2-a2*c1)/(a1*b2-a2*b1);return Point(x,y); } map<pair<double,double>,int> m; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf %lf",&e[i].x,&e[i].y);}Point o=Point(0,0);int ans=0;for(int i=1;i<=n;i++){m.clear();for(int j=1;j<=n;j++){if(e[i].x*e[j].y-e[j].x*e[i].y<=eqs) continue;//如果平行 Point oo=Circum(o,e[i],e[j]);ans=max(++m[make_pair(oo.x,oo.y)],ans);}}printf("%d\n",ans+1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Boundary（2020多校第二场B）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。