首页 > 代码库 > 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;}
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;}
的
Geometry
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。