almost 4 years ago

谨在此奉上一份模板……

老因为c++会强制自动类型转换导致int传给了point……sigh
还是每个细节都做不好……真是难过
--------------------萌萌哒分割线---------------------------------------------------------
tricky:为了避免四点共面加入了小扰动,但是在处理体积blahblah的时候要用原点,所以三角形存的是点的标号,千万注意不要直接减,以为这个debug了好久。但是对重点需要去重。
主要思想就是增量法。不断往凸包集合里加点。然后就是计算几何一系列知识了

bzoj1964

题意:求凸包,体积。

"bzoj1964"
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cstring>
#define maxn 1001
#define eps (1e-5)
using namespace std;
int can[maxn][maxn];double result=0;
struct point{
    double x,y,z;
    point(double xx=0.0,double yy=0.0,double zz=0.0)
    {
        x=xx;y=yy;z=zz;
    }
};
point CROSS(double x1,double y1,double z1,double x2,double y2,double z2)
{
    return point(y1*z2-y2*z1,z1*x2-z2*x1,x1*y2-x2*y1);
}
point operator *(point a,point b)
{
    return CROSS(a.x,a.y,a.z,b.x,b.y,b.z);
}
double operator ^(point a,point b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}
point operator -(point a,point b){return point(a.x-b.x,a.y-b.y,a.z-b.z);}
point operator +(point a,point b){return point(a.x+b.x,a.y+b.y,a.z+b.z);} 
point a[maxn],b[maxn];
struct triangle
{
    int t[3];
    triangle(int a=0,int b=0,int c=0) {t[0]=a;t[1]=b;t[2]=c;}
    point normal()
    {
        return (b[t[1]]-b[t[0]])*(b[t[2]]-b[t[0]]);
    }
    int isin(int x)
    {
        return ((b[x]-b[t[0]])^(normal()))>0?1:0;
    }
};
triangle r[maxn],temp[maxn];
int n=0,rn=0,tempn=0;
double rand01()
{
    return rand()/32766.0;
}
double randpoint(double x)
{
    return (x+(rand01()-0.5)*eps);
}
double fabs(double x)
{
    if (x>0) return x;return -x;
}
point makeeps(point p)
{
    return point(randpoint(p.x),randpoint(p.y),randpoint(p.z));
}
void ch3d()
{
    int i,j,x,k,p;
    r[1]=triangle(1,2,3);
    r[2]=triangle(3,2,1);
    rn=2;
    for (i=4;i<=n;i++)
    {
        tempn=0;
        for (j=1;j<=rn;j++)
        {
            x=r[j].isin(i);
            if (x==0) temp[++tempn]=r[j];
            for (k=0;k<3;k++)
                can[r[j].t[k]][r[j].t[(k+1)%3]]=x; 
        }
        for (j=1;j<=rn;j++)
        {
            int *a=r[j].t;
            for (k=0;k<3;k++)
            {
                if((can[a[k]][a[(k+1)%3]]^can[a[(k+1)%3]][a[k]]==1)&&can[a[k]][a[(k+1)%3]])
                    temp[++tempn]=triangle(a[k],a[(k+1)%3],i);
            }
        }
        for (j=1;j<=tempn;j++) r[j]=temp[j];
        rn=tempn;
    }
}
int dcmp(double x,double y)
{
    if (fabs(x-y)<eps) return 0;
    if (x<y) return -1;
    if (x>y) return 1;
}
bool cmp(point p,point q)
{
    return (dcmp(p.x,q.x)==0&&dcmp(p.y,q.y)==0&&dcmp(p.z,q.z)==0);
}
double V(point a,point b,point c,point d)
{
    return (((b-a)*(c-a))^(d-a))/6.0;
}
double calc(triangle x,int y)
{
    return fabs(V(a[x.t[0]],a[x.t[1]],a[x.t[2]],a[y]));
}
int main()
{
    int i,j,flag,p,k;point o;
    srand(23333);
    n=1;
    while (scanf("%lf%lf%lf",&a[n].x,&a[n].y,&a[n].z)==3) 
        n++;
    n--;
    for (i=1;i<=n;i++)
    {
        flag=0;
        for (j=i+1;j<=n;j++)
            if (cmp(a[i],a[j]))
            {
                flag=1;
                break;
            }
        if (flag) {o=a[i];a[i]=a[n];a[n]=o;i--;n--;}
    }
    for (i=1;i<=n;i++)
    {
        b[i]=makeeps(a[i]);
    }
    ch3d();
    p=r[1].t[0];
    for (i=1;i<=rn;i++)
    {
        flag=0;
        for (k=0;k<3;k++)
            if (r[i].t[k]==p){flag=1;break;}
        if (flag) continue;
        result+=calc(r[i],p);
    }
    printf("%.2lf\n",result);
}

hdu4266

题意:求凸包。给出点到凸包的最近距离。

"hdu4266"
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 1001
#define eps (1e-5)
using namespace std;
int can[maxn][maxn];double result=0;
struct point{
    double x,y,z;
    point(double xx=0.0,double yy=0.0,double zz=0.0){x=xx;y=yy;z=zz;}
    double length()   {return sqrt(x*x+y*y+z*z);}
};
point CROSS(double x1,double y1,double z1,double x2,double y2,double z2)
{
    return point(y1*z2-y2*z1,z1*x2-z2*x1,x1*y2-x2*y1);
}
point operator *(point a,point b)
{
    return CROSS(a.x,a.y,a.z,b.x,b.y,b.z);
}
double operator ^(point a,point b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}
point operator /(point a,double b) {return point(a.x/b,a.y/b,a.z/b);}
point operator -(point a,point b){return point(a.x-b.x,a.y-b.y,a.z-b.z);}
point operator +(point a,point b){return point(a.x+b.x,a.y+b.y,a.z+b.z);} 
point a[maxn],b[maxn];
struct triangle
{
    int t[3];
    triangle(int a=0,int b=0,int c=0) {t[0]=a;t[1]=b;t[2]=c;}
    point normal()
    {
        return (b[t[1]]-b[t[0]])*(b[t[2]]-b[t[0]]);
    }
    point enormal()
    {
        point k=(b[t[1]]-b[t[0]])*(b[t[2]]-b[t[0]]);;
        return k/k.length();
    }
    int isin(int x)
    {
        return ((b[x]-b[t[0]])^(normal()))>0?1:0;
    }
};
triangle r[maxn],temp[maxn];
int n=0,rn=0,tempn=0,m;
double rand01()
{
    return rand()/32766.0;
}
double randpoint(double x)
{
    return (x+(rand01()-0.5)*eps);
}
double fabs(double x)
{
    if (x>0) return x;return -x;
}
point makeeps(point p)
{
    return point(randpoint(p.x),randpoint(p.y),randpoint(p.z));
}
void ch3d()
{
    int i,j,x,k,p;
    r[1]=triangle(1,2,3);
    r[2]=triangle(3,2,1);
    rn=2;
    for (i=4;i<=n;i++)
    {
        tempn=0;
        for (j=1;j<=rn;j++)
        {
            x=r[j].isin(i);
            if (x==0) temp[++tempn]=r[j];
            for (k=0;k<3;k++)
                can[r[j].t[k]][r[j].t[(k+1)%3]]=x; 
        }
        for (j=1;j<=rn;j++)
        {
            int *a=r[j].t;
            for (k=0;k<3;k++)
            {
                if((can[a[k]][a[(k+1)%3]]^can[a[(k+1)%3]][a[k]]==1)&&can[a[k]][a[(k+1)%3]])
                    temp[++tempn]=triangle(a[k],a[(k+1)%3],i);
            }
        }
        for (j=1;j<=tempn;j++) r[j]=temp[j];
        rn=tempn;
    }
}
int dcmp(double x,double y)
{
    if (fabs(x-y)<eps) return 0;
    if (x<y) return -1;
    if (x>y) return 1;
}
bool cmp(point p,point q)
{
    return (dcmp(p.x,q.x)==0&&dcmp(p.y,q.y)==0&&dcmp(p.z,q.z)==0);
}
double V(point a,point b,point c,point d)
{
    return (((b-a)*(c-a))^(d-a))/6.0;
}
double calc(triangle x,int y)
{
    return fabs(V(a[x.t[0]],a[x.t[1]],a[x.t[2]],a[y]));
}
int read()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
void calcv()
{
    int i,flag,k,p;double result=0.0;
    p=r[1].t[0];
    for (i=1;i<=rn;i++)
    {
        flag=0;
        for (k=0;k<3;k++)
            if (r[i].t[k]==p){flag=1;break;}
        if (flag) continue;
        result+=calc(r[i],p);
    }
    printf("%.2lf\n",result);
}
void change()
{
    for (int i=1;i<=n;i++)       b[i]=makeeps(a[i]);
}
double PointToFlat(triangle tri,point p)
{
    return fabs(tri.enormal()^(p-b[tri.t[0]]));
}
int main()
{
    int i,j,flag,k;point o;point p;
    srand(23333);
    while (true)
    {
        n=read();
        if(n==0) break; 
        for (i=1;i<=n;i++)
            {a[i].x=read();a[i].y=read();a[i].z=read();}
        for (i=1;i<=n;i++)
        {
            flag=0;
            for (j=i+1;j<=n;j++)
            if (cmp(a[i],a[j]))
            {
                flag=1;
                break;
            }
            if (flag) {o=a[i];a[i]=a[n];a[n]=o;i--;n--;}
        }
        for (i=1;i<=n;i++) b[i]=a[i];
        ch3d();
        m=read();
        for (i=1;i<=m;i++)
        {
            p.x=read();p.y=read();p.z=read();
            result=1000000.0;
            for (j=1;j<=rn;j++)
                result=min(result,PointToFlat(r[j],p));
            printf("%.4lf\n",result);
        }
    }
}
← 【bzoj2178】【辛普森积分】圆的面积并 【bzoj3689】【XORthinking/可持久化trie+堆】异或之 →
 
comments powered by Disqus