[POI2007]对称轴Axes of Symmetry-osi 计算几何+KMP
BZOJ2331:[SCOI2011]地板 插头dp

BZOJ2829:信用卡凸包 计算几何+凸包+坐标变换

shinbokuow posted @ Feb 27, 2015 01:38:12 PM in BZOJ with tags 计算几何 凸包 坐标变换 , 1182 阅读

思路:

我们发现最终的答案就是缩小一圈后的矩形的顶点们形成的凸包的周长再加上一个半径为\(r\)的圆的周长.

因为多边形外角和为\(360\)度.这个不用多说.

 

此外还有一点点问题就是旋转后的坐标变换.

如果是\((x,y)\)以原点为旋转中心逆时针旋转\(\alpha\)弧度,那么新的坐标为\((xcos\alpha-ysin\alpha,xsin\alpha+ycos\alpha)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define N 200010
 
static const f2 eps=1e-8;
inline int dcmp(const f2&x){return (fabs(x)<eps)?0:(x<0?-1:1);}
 
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
     
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
    Point operator/(const f2&p)const{return Point(x/p,y/p);}
     
    bool operator<(const Point&B)const{return dcmp(x-B.x)==0?(dcmp(y-B.y)<0):(dcmp(x-B.x)<0);}
}P[N<<2],PP[N<<2],stk[N<<2];
 
f2 getdis(const Point&a,const Point&b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
Point move(const Point&p,const f2&Ang,const f2&x,const f2&y){
    return Point(p.x*cos(Ang)-p.y*sin(Ang)+x,p.x*sin(Ang)+p.y*cos(Ang)+y);
}
 
int main(){
    int n;scanf("%d",&n);
     
    f2 a,b,r,x,y,Ang;scanf("%lf%lf%lf",&a,&b,&r);a-=2*r,b-=2*r;
     
    register int i,j;
    int cnt=0;
    for(i=1;i<=n;++i){
        scanf("%lf%lf%lf",&x,&y,&Ang);
         
        P[++cnt]=move(Point(b/2,a/2),Ang,x,y);
        P[++cnt]=move(Point(-b/2,a/2),Ang,x,y);
        P[++cnt]=move(Point(b/2,-a/2),Ang,x,y);
        P[++cnt]=move(Point(-b/2,-a/2),Ang,x,y);
    }
     
    int top=0;
    sort(P+1,P+cnt+1);
    int revins;for(revins=cnt;revins!=1&&P[revins].x==P[revins-1].x;--revins);
    for(i=revins;i<=(n+revins)/2;++i)swap(P[i],P[n+revins-i]);
     
    for(i=1;i<=cnt;++i){
        if(!top)stk[++top]=P[i];
        else{while(top>1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
    }
    int nowtop=top;
    for(i=revins-1;i>=1;--i){
        if(top==nowtop)stk[++top]=P[i];
        else{while(top>=nowtop+1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
    }--top;
     
    f2 re=0;
    for(i=1;i<top;++i)re+=getdis(stk[i],stk[i+1]);re+=getdis(stk[top],stk[1]);
     
    printf("%.2lf",re+2*acos(-1.0)*r);
     
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter