• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

1.题意

对于一些相同的信用卡,本质上是圆,求所有信用卡的圆心作为点集,求这个点集的凸包的周长。

2.思路

其实这个问题没那么难。

不能凸包或计算几何,参见https://www.luogu.com.cn/problem/P2742,或https://oi-wiki.org//geometry/'s的解释。

其实如果信用卡是矩形的,可以直接提取矩形的所有点,运行一个凸包算法。这个问题的难点在于,信用卡是一个圆,我们取出的点可能是一个$\frac{1}{4}$圆,所以不能正常使用凸包算法。

说白了,我们像下图一样要求封闭线的长度。

4d3i1uaqwvh3536.png

看上图,很容易发现,圆与直线重合的部分都是这个圆的切线。我们知道,圆的切线垂直于通过其切点的半径。

观察每个圈子,发现重要规律。

y1vofhgfxup3537.png

如上图所示,$\alpha$为圆心角。因为切线是垂直的,所以找到了一个对角互补的四边形!

而$\beta$,恰好是外角,所以$\alpha=\beta$。

因为多边形的外角之和是360美元,$\beta$加起来是360美元。

因此,$\alpha$加起来是$360 $。

在整个图形中,所有的圆都是相等的,所以我们可以看到,所有用切线连接的圆构成了一个完整的圆。

这样问题就解决了一半,弧的总长度是$2r$。

剩下的问题是求所有直边的长度。

p0tcczw40k33538.png

根据直角平移,我们很容易得出结论:求所有中心点的一个凸包就是所有直边的长度。

直线长度加上圆的周长就是答案。至此,这个问题问完了。

3.代码

#includebits/stdc。h

使用命名空间std

int n,tx[]={1,1,-1,-1},ty[]={1,-1,1,-1},cnt,stk[100005],top

布尔维斯[100005];

双a,b,r,xx,yy,zz,res

pairdouble,double q[100005];

pairdouble,double rotate(pairdouble,double a,double b){

return { a . first * cos(b)a . second * sin(b),-a . first * sin(b)a . second * cos(b)};

}

pairdouble,double运算符-(pairdouble,double a,pairdouble,double b){

return {a.first-b.first,a . second-b . second };

}

双交叉(pairdouble,double a,pairdouble,double b){

返回a . first * b . second-a . second * b . first;

}

double area(pairdouble、double a、pairdouble、double b、pairdouble、double c){

回交(b-a,c-a);

}

double get_dist(pairdouble,double a,pairdouble,double b){

double dx=a.first-b.first,dy=a . second-b . second;

返回sqrt(dx * dx dy * dy);

}

int main(){

scanf('%d%lf%lf%lf ',n,a,b,r);

a=a/2-r;

b=b/2-r;

for(int I=1;I=n;i ){

scanf('%lf%lf%lf ',xx,yy,ZZ);

for(int I=0;i4;i ){

pairdouble,double temp=rotate({tx*b,ty*a},-ZZ);

q[CNT]={临时第一个xx,临时第二个YY };

}

}

sort(q,q CNT);

for(int I=0;icnti ){

while(top=2area(q[stk[top-1]],q[stk[top]],q)=0){

vis[STK[top-]]=0;

}

STK[top]=I;

vis=1;

}

vis[0]=0;

for(int I=CNT-1;I=0;我- ){

if(vis){

继续;

}

while(top=2area(q[stk[top-1]],q[stk[top]],q)=0){

top-;

}

STK[top]=I;

}

for(int I=2;i=topi ){

res=get_dist(q[stk[i-1]],q[STK]);

}

printf('%.2lf ',RES 2 * 3.141592653589793 * r);

返回0;

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now