首页 > 代码库 > Geometry

Geometry

uva1473 这题说的是 在空间中给了n个点 然后用体积最小的圆锥将这些点包含在内可以在表面上, 将这些点 映射到xoz平面上然后,然后枚举每个上凸包的边和每个点的极值进行判断求得最小的体积 我们会发现最小的体积 要不就紧贴一个点要不然就会贴住两个点

#include <iostream>#include <cstdio>#include <string.h>#include <cmath>#include <algorithm>using namespace std;const double INF =1.79769e+308;const double eps = 0.000000000001;int dcmp(double a){     if(fabs(a)<=eps) return 0;     return a>0?1:-1;}struct point {   double x,y;   point(double a=0, double b=0){       x=a; y=b;   }   point operator -(point A){     return point(x-A.x, y-A.y);   }   bool operator <(point A)const{      return dcmp(x-A.x)<0||(dcmp(x-A.x)==0&&dcmp(y-A.y)<=0);   }}P[10005],ch[10005];int n;double Cross(point A, point B){     return A.x*B.y-A.y*B.x;}int Conxtull(int &G){    sort(P,P+n);    int m=0;    for(int i =0; i<n ; ++i )    {        while(m>1&&dcmp( Cross( ( ch[m-1] - ch[m-2] ), ( P[i] - ch[m-2] ) ) )<=0)m--;        ch[ m++ ] = P[i];    }    int k = m;    for(int i = n-2; i>=0; --i )        {             while( k<m&&dcmp( Cross( ch[m-1]-ch[m-2], P[i]-ch[m-2] ) )<=0 ) m--;              ch[m++] = P[i] ;        }        if(n>1)m--;        G=m;        return k-1;}point getpoint(double k,point F){      point ans;      ans.x = F.x+(F.y/k);      ans.y = F.y+k*F.x;      return ans;}double Volun(double radio, double hight){      return  acos(-1)*radio*radio*hight/3.0;}double Volume,ansR,ansH;void solve(double k,point T){       point e = getpoint(k,T);       double V =Volun(e.x,e.y);       if(dcmp(Volume-V)>0){          ansR=e.x; ansH=e.y;          Volume=V;       }}int main(){      freopen("data.in","r",stdin);      freopen("data.out","w",stdout);     while(scanf("%d",&n)==1)        {            n++;             double Minx=0.0;             P[0]=point(0,0);               for(int i =1 ; i<n; ++i)                {                     double x,y,z;                     scanf("%lf%lf%lf",&x,&y,&z);                     P[i].x=sqrt(x*x+y*y);                     P[i].y=z;                     Minx = max(Minx,P[i].x);                }                int m;                int k =Conxtull(m);                ch[m]=ch[0];                Volume=INF;                double K=INF;                int we;                for(int i=k; i<m; ++i )                {                     if(i==m-1||dcmp(ch[i].x-ch[i+1].x)<=0||dcmp(ch[i].y-ch[i+1].y)>=0)                     {                            we=i;                            break;                     }                     double R =(ch[i+1].y-ch[i].y)/(ch[i].x-ch[i+1].x);                     double t =ch[i].y*2;                     t/=ch[i].x;                     int f1 =dcmp(t-R);                     int f2=dcmp(t-K);                     if(f1>=0&&f2<=0)                       solve(t,ch[i]);                      solve(R,ch[i]);                      K=R;                }                double t = 2.0*ch[we].y/ch[we].x;                if(dcmp(t-K)<0)                    solve(t,ch[we]);                printf("%.3lf %.3lf\n",ansH,ansR);        }     return 0;}
View Code

uva 12165 这题说的是  用梅涅劳斯 计算图中三角形的对应的比例列出一堆后 开始拆分那些边然后化简就会达到所要的公式

#include <iostream>#include <string.h>#include <cmath>#include <cstdio>using namespace std;struct point{    double  x,y;    point(double a=0,double b=0){       x=a; y =b;    }    point operator +(point A){       return point(x+A.x,y+A.y);    }    point operator -(point A){         return point(x-A.x,y-A.y);    }    point operator *(double  A){          return point(x*A,y*A);    }};double Cross(point A,point B){   return A.x*B.y-A.y*B.x;}double Dot(point A,point B){   return A.x*B.x+A.y*B.y;}double Length(point A){   return sqrt(Dot(A,A));}int main(){      double m1,m2,m3,m4,m5,m6;      point P,Q,R;      int cas;      scanf("%d",&cas);      for(int cc=1; cc<=cas; ++cc){           scanf("%lf%lf%lf%lf%lf%lf",&P.x,&P.y,&Q.x,&Q.y,&R.x,&R.y);           scanf("%lf%lf%lf%lf%lf%lf",&m1,&m2,&m3,&m4,&m5,&m6);           double c =Length(P-Q),a =Length(R-Q), b =Length(P-R);           double m = m3*m5/(m6*(m3+m4));           double n = m4*m2/((m3+m4)*m1);           double BP = (c+m*c)/(n-m);           m = (m5*m1)/((m5+m6)*m2);           n = m6*m4/((m5+m6)*m3);           double CQ = (m*a+a)/(n-m);           m = m1*m3/((m1+m2)*m4);           n =m2*m6/((m1+m2)*m5);           double AR = (m*b+b)/(n-m);           point PR = (R-P)*(1/Length(R-P));           point A = R +(PR*AR);           point QP = (P-Q)*(1/Length(P-Q));           point B = P+(QP*BP);           point RQ = (Q-R)*(1/Length(Q-R));           point C = Q+(RQ*CQ);           printf("%.8lf %.8lf %.8lf %.8lf %.8lf %.8lf\n",A.x,A.y,B.x,B.y,C.x,C.y);     }      return 0;}
View Code

Geometry