美文网首页
计算几何

计算几何

作者: 云中翻月 | 来源:发表于2019-08-26 21:20 被阅读0次

极限

POJ 1981: Circle and Points

根据CD两点和半径确定的两个圆，求解圆心坐标的过程
题解链接
https://www.cnblogs.com/weeping/p/7655975.html
https://blog.csdn.net/fp_hzq/article/details/7972428
注意atan等反三角函数的应用和圆上的几何关系。
代码如下 
/*
题解链接 
https://www.cnblogs.com/weeping/p/7655975.html
https://blog.csdn.net/fp_hzq/article/details/7972428
注意atan等反三角函数的应用和圆上的几何关系。 
*/
#define method_2
#ifdef method_1
/*
2700msAC 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
struct node {
    double x,y;
    bool operator<(const node& h)const {
        return x<h.x||(abs(x-h.x)<eps&&y<h.y);
    }
} p[maxn];
int n,ans;
void init() {
    ans=1;
}
double dis(node i,node j) { //计算i和j距离的平方
    return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y);
}
int solve(node a,node b) {
    node tmp;
    tmp.x=(a.x+b.x)/2,tmp.y=(a.y+b.y)/2;
    double angle=acos(-1.0)/2+atan2(a.y-b.y,a.x-b.x);
    double len=sqrt(1-dis(a,b)/4);
    tmp.x+=cos(angle)*len;
    tmp.y+=sin(angle)*len;
    int res=0;
    for(int i=1; i<=n; i++) {
        if(dis(p[i],tmp)<=1+eps) res++;
    }
//  D(angle);D(res);E;
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Circle and Points.in","r",stdin);
    while(cin>>n) {
        if(!n) break;
        for(int i=1; i<=n; i++) cin>>p[i].x>>p[i].y;
        if(n==1) {
            cout<<1<<endl;
            continue;
        }
        init();
        sort(p+1,p+n+1);
        for(int i=1; i<=n; i++) for(int j=i+1; j<=n&&(p[j].x-p[i].x)<=2; j++) if(dis(p[i],p[j])<=4) {
                    ans=max(ans,max(solve(p[i],p[j]),solve(p[j],p[i])));
                }
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*
800msAC 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
struct node {
    double x,y;
} p[maxn];
struct arc {
    int flag;
    double rad;
    bool operator<(const arc& h)const {
        return rad<h.rad;
    }
} q[maxn<<1];
int n,ans;
void init() {
    ans=1;
}
double dis(node i,node j) { //计算i和j距离的平方
    return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y);
}
void solve() {
    for(int i=1; i<=n; i++) {
        int cnt=0,res=0;
        double dist;
        for(int j=1; j<=n; j++) {
            if((dist=dis(p[i],p[j]))<=4&&i!=j) { //这边不能写成 (dist=dis(p[i],p[j])<=4)&&i!=j
                double rad=acos(sqrt(dist)/2);
                double tmp=atan2(p[j].y-p[i].y,p[j].x-p[i].x);
                q[++cnt].flag=1;
                q[cnt].rad=tmp-rad;
                q[++cnt].flag=0;
                q[cnt].rad=tmp+rad;
            }
        }
        sort(q+1,q+cnt+1);
        for(int j=1; j<=cnt; j++) {
            if(q[j].flag) res++;
            else res--;
            ans=max(ans,res+1);//包括i点
//          D(q[j].flag);D(q[j].rad);E;
        }
//      D(res);E;
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Circle and Points.in","r",stdin);
    while(cin>>n) {
        if(!n) break;
        for(int i=1; i<=n; i++) cin>>p[i].x>>p[i].y;
        if(n==1) {
            cout<<1<<endl;
            continue;
        }
        init();
        solve();
        cout<<ans<<endl;
    }
    return 0;
}
#endif

POJ 1418: Viva Confetti
题解链接 http://www.hankcs.com/program/algorithm/poj-1418-viva-confetti.html
两层抽象：
1 将区域抽象为圆弧构成的区域。
2 通过判断圆弧的中点，来判断是否遮盖（圆弧用极角表示，另需加入弧度为0和2Π的圆弧，使得所有圆弧都会被考虑到）
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 http://www.hankcs.com/program/algorithm/poj-1418-viva-confetti.html
两层抽象：
1 将区域抽象为圆弧构成的区域。
2 通过判断圆弧的中点，来判断是否遮盖（圆弧用极角表示，另需加入弧度为0和2Π的圆弧，使得所有圆弧都会被考虑到） 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
const double eps=4e-13;
const double pi=acos(-1.0);
struct node{
    double x,y,r;
}a[maxn];
int n,cnt,vis[maxn],ans;
double rad[maxn*maxn];
void init(){
    ans=0;
    memset(vis,0,sizeof(vis));
}
double normalizeangle(double angle){
    if(angle<0) angle+=2*pi;
    if(angle>=2*pi) angle-=2*pi;
    return angle;
}
int hit(double x,double y){
    for(int i=n;i>=1;i--){
        if(a[i].r*a[i].r>(x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y)) return i;
    }
    return -1;
}
double dis(int i,int j){
    return (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Viva Confetti.in","r",stdin);
    while(cin>>n){
        if(!n) break;
        init();
        for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].r;
        for(int i=1;i<=n;i++){
            cnt=0;
            rad[++cnt]=0.0,rad[++cnt]=2.0*pi;
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                if((a[i].r+a[j].r<sqrt(dis(i,j)))||(a[i].r+sqrt(dis(i,j))<a[j].r)||(sqrt(dis(i,j))+a[j].r<a[i].r)) continue;
                double d=atan2(a[j].y-a[i].y,a[j].x-a[i].x);
                double e=acos((a[i].r*a[i].r+dis(i,j)-a[j].r*a[j].r)/(2*a[i].r*sqrt(dis(i,j))));
                rad[++cnt]=normalizeangle(d+e),rad[++cnt]=normalizeangle(d-e);
            }
            sort(rad+1,rad+cnt+1);
            for(int j=1;j<=cnt-1;j++){
                double angle=(rad[j]+rad[j+1])/2.0;
                for(int k=-1;k<=1;k+=2){
                    int res=hit(a[i].x+cos(angle)*(a[i].r+eps*k),a[i].y+sin(angle)*(a[i].r+eps*k));
                    if(res!=-1) vis[res]=1;
                }
            }
        }
        for(int i=1;i<=n;i++) if(vis[i]) ans++;
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

平面扫描

POJ 3168: Barn Expansion
题解链接 https://blog.csdn.net/aozil_yang/article/details/52060501
其中method_1未通过，反例见代码注释。
代码如下

/*
题解链接 https://blog.csdn.net/aozil_yang/article/details/52060501
*/
#define method_3
#ifdef method_1
/*
这个方法有错，反例如下。
3
1 0 2 5
0 1 1 2
0 3 1 4 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=25000+5;
const int INF=0x3f3f3f3f;
int n,cntx=0,cnty=0,flag[maxn]={0},ans=0;
struct nodex{
    int x,y1,y2,id;
    bool operator<(const nodex& h)const{return x!=h.x?x<h.x:y1<h.y1;}
}linex[maxn<<1];
struct nodey{
    int y,x1,x2,id;
    bool operator<(const nodey& h)const{return y!=h.y?y<h.y:x1<h.x1;}
}liney[maxn<<1];
inline bool overlap(int i,int j,int f){
    if(f==0){
        return linex[j].y1<=linex[i].y2;
    }
    if(f==1){
        return liney[j].x1<=liney[i].x2;
    }
} 
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Barn Expansion.in","r",stdin);
    scanf("%d",&n);
    int x1,y1,x2,y2;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        linex[++cntx].x=x1,linex[cntx].y1=y1,linex[cntx].y2=y2,linex[cntx].id=i;
        linex[++cntx].x=x2,linex[cntx].y1=y1,linex[cntx].y2=y2,linex[cntx].id=i;
        liney[++cnty].y=y1,liney[cnty].x1=x1,liney[cnty].x2=x2,liney[cnty].id=i;
        liney[++cnty].y=y2,liney[cnty].x1=x1,liney[cnty].x2=x2,liney[cnty].id=i;
    }
    sort(linex+1,linex+cntx+1);
    sort(liney+1,liney+cnty+1);
    for(int i=1;i<=cntx-1;i++){
//      D(linex[i].x);D(linex[i].y1);D(linex[i].y2);E;
        if(linex[i].x!=linex[i+1].x) continue;
        if(overlap(i,i+1,0)) flag[linex[i].id]=flag[linex[i+1].id]=1;
    }
    for(int i=1;i<=cnty-1;i++){
        if(liney[i].y!=liney[i+1].y) continue;
        if(overlap(i,i+1,1)) flag[liney[i].id]=flag[liney[i+1].id]=1;
    }
    for(int i=1;i<=n;i++) if(flag[i]==0){
//      D(i);E;
        ans++;
    }
    printf("%d",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=25000+5;
const int INF=0x3f3f3f3f;
int n,cntx=0,cnty=0,flag[maxn]={0},ans=0;
struct nodex{
    int x,y1,y2,id;
//  bool operator<(const nodex& h)const{return x!=h.x?x<h.x:y1<h.y1;}
}linex[maxn<<1];
struct nodey{
    int y,x1,x2,id;
//  bool operator<(const nodey& h)const{return y!=h.y?y<h.y:x1<h.x1;}
}liney[maxn<<1];
bool cmpx(nodex i,nodex j){
    return (i.x<j.x)||(i.x==j.x&&i.y1<j.y1);
}
bool cmpy(nodey i,nodey j){
    return (i.y<j.y)||(i.y==j.y&&i.x1<j.x1);
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Barn Expansion.in","r",stdin);
    scanf("%d",&n);
    int x1,y1,x2,y2;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        linex[++cntx].x=x1,linex[cntx].y1=y1,linex[cntx].y2=y2,linex[cntx].id=i;
        linex[++cntx].x=x2,linex[cntx].y1=y1,linex[cntx].y2=y2,linex[cntx].id=i;
        liney[++cnty].y=y1,liney[cnty].x1=x1,liney[cnty].x2=x2,liney[cnty].id=i;
        liney[++cnty].y=y2,liney[cnty].x1=x1,liney[cnty].x2=x2,liney[cnty].id=i;
    }
    sort(linex+1,linex+cntx+1,cmpx);
    sort(liney+1,liney+cnty+1,cmpy);
    for(int i=1;i<=cntx;i++){
//      D(linex[i].x);D(linex[i].y1);D(linex[i].y2);E;
        int nxt_i=cntx;
        for(int j=i+1;j<=cntx;j++) if(linex[i].x!=linex[j].x){
            nxt_i=j-1;break;
        }
        int up=linex[i].y2;
        for(int j=i+1;j<=nxt_i;j++){
            if(linex[j].y1<=up){
                flag[linex[j].id]=flag[linex[j-1].id]=1;
            }
            if(linex[j].y2>=up){
                up=linex[j].y2;
            }
        }
        i=nxt_i; //这句话保证对于每条线只处理一次，即保证处理过程复杂度为O(n) 
    }
    for(int i=1;i<=cnty;i++){
        int nxt_i=cnty;
        for(int j=i+1;j<=cnty;j++) if(liney[i].y!=liney[j].y){
            nxt_i=j-1;break;
        }
        int up=liney[i].x2;
        for(int j=i+1;j<=nxt_i;j++){
            if(liney[j].x1<=up){
                flag[liney[j].id]=flag[liney[j-1].id]=1;
            }
            if(liney[j].x2>=up){
                up=liney[j].x2;
            }
        }
        i=nxt_i; //这句话保证对于每条线只处理一次，即保证处理过程复杂度为O(n) 
    }
    for(int i=1;i<=n;i++) if(flag[i]==0){
//      D(i);E;
        ans++;
    }
    printf("%d",ans);
    return 0;
} 
#endif

POJ 3293: Rectilinear polygon
题解链接 http://www.mamicode.com/info-detail-1716765.html
代码如下

/*

*/
#define method_1 
#ifdef method_1
/*
题解链接 http://www.mamicode.com/info-detail-1716765.html 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int T,n,con[maxn][2],lcnt,ans;
struct node{
    int x,y,id;
}p[maxn];
struct nodex{
    int x,y1,y2;
}linex[maxn];
bool cmpx(node i,node j){
    return i.x!=j.x?i.x<j.x:i.y<j.y;
}
bool cmpy(node i,node j){
    return i.y!=j.y?i.y<j.y:i.x<j.x;
}
void init(){
    ans=0,lcnt=0;
}
bool check(node i,node j){ //判断点i和点j组成的横线是否与之前的任意一条竖线相交 
    int x1=i.x,x2=j.x,y=i.y;
    for(int i=1;i<=lcnt;i++){
        if(x1<linex[i].x&&x2>linex[i].x&&y<linex[i].y2&&y>linex[i].y1) return true;
    }
    return false;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Rectilinear polygon.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
        sort(p+1,p+n+1,cmpx);
        int flag=0,cnt=1;
        for(int i=2;i<=n&&!flag;i++){
            if(p[i].x!=p[i-1].x){
                if(cnt&1) flag=1;
                cnt=1;
            }
            else{
                cnt++;
                if((cnt&1)==0){
                    ans+=p[i].y-p[i-1].y;
                    con[p[i].id][0]=p[i-1].id;
                    con[p[i-1].id][0]=p[i].id;
                    linex[++lcnt].x=p[i].x,linex[lcnt].y1=p[i-1].y,linex[lcnt].y2=p[i].y;
                }
            }
        }
        sort(p+1,p+n+1,cmpy);
        cnt=1;
        for(int i=2;i<=n&&!flag;i++){
            if(p[i].y!=p[i-1].y){
                if(cnt&1) flag=1;
                cnt=1;
            }
            else{
                cnt++;
                if((cnt&1)==0){
                    ans+=p[i].x-p[i-1].x;
                    con[p[i].id][1]=p[i-1].id;
                    con[p[i-1].id][1]=p[i].id;
                    if(check(p[i-1],p[i])) flag=1;
                }
            }
        }
        //依次连接各个直角顶点
        int pcnt=0,t=0,x=1;
        while(1){
            x=con[x][t];
            t^=1;
            pcnt++;
            if(x==1||flag) break; //x==1表示连回自身 
        } 
        if(pcnt!=n) flag=1; //图不连通 
        if(flag) printf("-1\n");
        else printf("%d\n",ans);
    }   
    return 0;
}
#endif

POJ 2482: Stars in Your Window
题解链接 https://www.jianshu.com/p/f598203aa288

相关文章

  • 计算几何

    球体积交 && 球体积并

  • 计算几何

    数据处理纪录

  • 计算几何

    极限 POJ 1981: Circle and Points POJ 1418: Viva Confetti题解链...

  • 计算几何

  • 计算几何汇总

    此篇以汇总计算几何资源与主体脉络，便于以后查询学习。计算几何，邓俊辉学堂在线Python中的计算几何 脉络 计算几...

  • 计算几何基础

    判断点是否在线段上、判断两条线段是否相交 这里采用向量的解法。有2个概念：向量的内积和外积。内积又称为点积dot ...

  • 计算几何模板

  • 计算几何初步

    一、叉积叉积的计算是线段方法的核心。对于向来p1和p2，叉积是由点(0,0)、p1、p2和p1+p2构成的平行四边...

  • 计算几何总结

    1、点积 a·b的几何意义为a在b上的投影长度乘以b的模, a·b=|a||b|cosθ,其中θ为a,b之间的夹角...

  • 计算几何-基础

    一个基于坐标系的几何画图网页，对于计算几何，这个网页用来画图、打草稿啥的挺好用。 向量 点积（内积） 线性代数中的...

网友评论

      本文标题：计算几何

      本文链接：https://www.haomeiwen.com/subject/vfsrjctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|计算几何|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！