程序员人生 网站导航

几何基础专题

栏目：php教程时间：2016-07-18 08:10:59


  • UVA 11437 Triangle Fun
  • UVA 11800 Determine the Shape 4边形判定
  • UVA 11646 Athletics Track
  • UVA 11817 Tunnelling the Earth 球面距离
  • UVA 1473 Dome of Circus
  • UVA 11524 InCircle
  • UVA 11731 Ex-circles 旁切圆
  • UVA 12300 Smallest Regular Polygon
  • UVA 10566 Crossed Ladders
  • UVA 11186 Circum Triangle
  • UVA 12165 Triangle Hazard


UVA 11437 Triangle Fun

#include using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector #define pi pair #define SI(a) ((a).size()) typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } ll sqr(ll a){return a*a;} ld sqr(ld a){return a*a;} double sqr(double a){return a*a;} ld PI = 3.141592653589793238462643383; class P{ public: double x,y; P(double x=0,double y=0):x(x),y(y){} friend long double dis2(P A,P B){return sqr(A.x-B.x)+sqr(A.y-B.y); } friend long double Dot(P A,P B) {return A.x*B.x+A.y*B.y; } friend long double Length(P A) {return sqrt(Dot(A,A)); } friend long double Angle(P A,P B) {return acos(Dot(A,B) / Length(A) / Length(B) ); } friend P operator- (P A,P B) { return P(A.x-B.x,A.y-B.y); } friend P operator+ (P A,P B) { return P(A.x+B.x,A.y+B.y); } friend P operator* (P A,double p) { return P(A.x*p,A.y*p); } friend P operator/ (P A,double p) { return P(A.x/p,A.y/p); } friend bool operator< (const P& a,const P& b) {return a.xconst double eps=1e⑴0; int dcmp(double x) { if (fabs(x)return 0; else return x<0 ? -1 : 1; } bool operator==(const P& a,const P& b) { return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y) == 0; } typedef P V; double Cross(V A,V B) {return A.x*B.y - A.y*B.x;} double Area2(P A,P B,P C) {return Cross(B-A,C-A);} V Rotate(V A,double rad) { return V(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); } // A 不是 0向量 V Normal(V A) { double L = Length(A); return V(-A.y/L , A.x/L); } namespace complex_G{ typedef complex<double> Point; //real(p):实部 imag(p):虚部 conj(p):共轭 typedef Point Vector; double Dot(Vector A,Vector B) {return real(conj(A)*B); } double Cross(Vector A,Vector B) {return imag(conj(A)*B); } Vector Rotate(Vector A,double rad) {return A*exp(Point(0,rad)); } } //Cross(v,w)==0(平行)时,不能调这个函数 P GetLineIntersection(P p,V v,P Q,V w){ V u = p-Q; double t = Cross(w,u)/Cross(v,w); return p+v*t; } P GetLineIntersectionB(P p,V v,P Q,V w){ return GetLineIntersection(p,v-p,Q,w-Q); } double DistanceToLine(P p,P A,P B) { V v1 = B-A, v2 = p-A; return fabs(Cross(v1,v2))/Length(v1); } double DistanceToSegment(P p,P A,P B) { if (A==B) return Length(p-A); V v1 = B-A, v2 = p-A, v3 = p - B; if (dcmp(Dot(v1,v2))<0) return Length(v2); else if (dcmp(Dot(v1,v3))>0 ) return Length(v3); else return fabs(Cross(v1,v2) ) / Length(v1); } P GetLineProjection(P p,P A,P B) { V v=B-A; return A+v*(Dot(v,p-A)/Dot(v,v)); } //规范相交-线段相交且交点不在端点 bool SegmentProperIntersection(P a1,P a2,P b1,P b2) { double c1 = Cross(a2-a1,b1-a1) , c2 = Cross(a2-a1,b2-a1), c3 = Cross(b2-b1,a1-b1) , c4 = Cross(b2-b1,a2-b1); return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0; } //点在线段上（不包括端点） bool OnSegment(P p,P a1,P a2) { return dcmp(Cross(a1-p,a2-p)) == 0 && dcmp(Dot(a1-p,a2-p))<0; } double PolygonArea(P *p,int n) { double area=0; For(i,n-2) area+=Cross(p[i]-p[0],p[i+1]-p[0]); return area/2; } /*欧拉公式： V+F-E=2 V-点数 F面数 E边数 */ P read_point() { P a; scanf("%lf%lf",&a.x,&a.y); return a; } struct C{ P c; double r,x,y; C(P c,double r):c(c),r(r),x(c.x),y(c.y){} P point(double a) { return P(c.x+cos(a)*r,c.y+sin(a)*r); } }; struct Line{ P p; V v; double ang; Line(){} Line(P p,V v):p(p),v(v) {ang=atan2(v.y,v.x); } bool operator<(const Line & L) const { return angdouble a) { return p+v*a; } }; int getLineCircleIntersection(Line L,C cir,double &t1,double &t2,vector

& sol) { if (dcmp(DistanceToLine(cir.c,L.p,L.p+L.v)-cir.r)==0) { sol.pb(GetLineProjection(cir.c,L.p,L.p+L.v)); return 1; } double a = L.v.x, b = L.p.x - cir.c.x, c = L.v.y, d= L.p.y - cir.c.y; double e = a*a+c*c, f = 2*(a*b + c*d), g = b*b+d*d-cir.r*cir.r; double delta = f*f - 4*e*g; if (dcmp(delta)<0) return 0; else if (dcmp(delta)==0) { t1 = t2 = -f / (2*e); sol.pb(L.point(t1)); return 1; } t1 = (-f - sqrt(delta)) / (2*e); sol.pb(L.point(t1)); t2 = (-f + sqrt(delta)) / (2*e); sol.pb(L.point(t2)); return 2; } double angle(V v) {return atan2(v.y,v.x);} int getCircleCircleIntersection(C C1,C C2,vector

& sol) { double d = Length(C1.c-C2.c); if (dcmp(d)==0) { if (dcmp(C1.r - C2.r)==0) return -1; //2圆重合 return 0; } if (dcmp(C1.r+C2.r-d)<0) return 0; if (dcmp(fabs(C1.r-C2.r)-d)>0) return 0; double a = angle(C2.c-C1.c); double da = acos((C1.r*C1.r+d*d - C2.r*C2.r)/ (2*C1.r*d)); P p1 = C1.point(a-da), p2 = C1.point(a+da); sol.pb(p1); if (p1==p2) return 1; sol.pb(p2); return 2; } // Tangents-切线 int getTangents(P p,C c,V* v) { V u= c.c-p; double dist = Length(u); if (distreturn 0; else if (dcmp(dist-c.r)==0) { v[0]=Rotate(u,PI/2); return 1; } else { double ang = asin(c.r / dist); v[0]=Rotate(u,-ang); v[1]=Rotate(u,ang); return 2; } } //这个函数假定整数坐标和整数半径 //double时要把int改成double int getTangents(C A,C B,P* a,P* b) { int cnt=0; if (A.rint d2 = (A.c.x-B.c.x)*(A.c.x-B.c.x) + (A.c.y-B.c.y)*(A.c.y-B.c.y); int rdiff = A.r-B.r; int rsum = A.r+B.r; if (d2return 0; double base = atan2(B.y-A.y,B.x-A.x); if (d2==0 && A.r == B.r) return -1; if (d2 == rdiff*rdiff) { a[cnt] = A.point(base); b[cnt] = B.point(base); ++cnt; return 1; } double ang = acos((A.r-B.r)/sqrt(d2)); a[cnt] = A.point(base+ang); b[cnt] = B.point(base+ang); ++cnt; a[cnt] = A.point(base-ang); b[cnt] = B.point(base-ang); ++cnt; if (d2==rsum*rsum) { a[cnt] = A.point(base); b[cnt] = B.point(PI+base); ++cnt; } else if (d2>rsum*rsum) { double ang = acos((A.r+B.r)/sqrt(d2)); a[cnt] = A.point(base+ang); b[cnt] = B.point(PI+base+ang); ++cnt; a[cnt] = A.point(base-ang); b[cnt] = B.point(PI+base-ang); ++cnt; } return cnt; } //Circumscribed-外接 C CircumscribedCircle(P p1,P p2,P p3) { double Bx = p2.x-p1.x, By= p2.y-p1.y; double Cx = p3.x-p1.x, Cy= p3.y-p1.y; double D = 2*(Bx*Cy-By*Cx); double cx = (Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D + p1.x; double cy = (Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D + p1.y; P p =P(cx,cy); return C(p,Length(p1-p)); } //Inscribed-内接 C InscribedCircle(P p1,P p2,P p3) { double a = Length(p2-p3); double b = Length(p3-p1); double c = Length(p1-p2); P p = (p1*a+p2*b+p3*c)/(a+b+c); return C(p,DistanceToLine(p,p1,p2)); } double torad(double deg) { return deg/180*acos(-1); } //把 角度+-pi 转换到 [0,pi) 上 double radToPositive(double rad) { if (dcmp(rad)<0) rad=ceil(-rad/PI)*PI+rad; if (dcmp(rad-PI)>=0) rad-=floor(rad/PI)*PI; return rad; } double todeg(double rad) { return rad*180/acos(-1); } //(R,lat,lng)->(x,y,z) void get_coord(double R,double lat,double lng,double &x,double &y,double &z) { lat=torad(lat); lng=torad(lng); x=R*cos(lat)*cos(lng); y=R*cos(lat)*sin(lng); z=R*sin(lat); } void print(double a) { printf("%.6lf",a); } void print(P p) { printf("(%.6lf,%.6lf)",p.x,p.y); } template<class T> void print(vector v) { sort(v.begin(),v.end()); putchar('['); int n=v.size(); Rep(i,n) { print(v[i]); if (i1) putchar(','); } puts("]"); } // 把直线沿v平移 // Translation-平移 Line LineTranslation(Line l,V v) { l.p=l.p+v; return l; } void CircleThroughAPointAndTangentToALineWithRadius(P p,Line l,double r,vector

& sol) { V e=Normal(l.v); Line l1=LineTranslation(l,e*r),l2=LineTranslation(l,e*(-r)); double t1,t2; getLineCircleIntersection(l1,C(p,r),t1,t2,sol); getLineCircleIntersection(l2,C(p,r),t1,t2,sol); } void CircleTangentToTwoLinesWithRadius(Line l1,Line l2,double r,vector

& sol) { V e1=Normal(l1.v),e2=Normal(l2.v); Line L1[2]={LineTranslation(l1,e1*r),LineTranslation(l1,e1*(-r))}, L2[2]={LineTranslation(l2,e2*r),LineTranslation(l2,e2*(-r))}; Rep(i,2) Rep(j,2) sol.pb(GetLineIntersection(L1[i].p,L1[i].v,L2[j].p,L2[j].v)); } void CircleTangentToTwoDisjointCirclesWithRadius(C c1,C c2,double r,vector

& sol) { c1.r+=r; c2.r+=r; getCircleCircleIntersection(c1,c2,sol); } P getP(P A,P B,P C) { P D=B+(C-B)/3; P E=C+(A-C)/3; return GetLineIntersection(A,D-A,B,E-B); } int main() { // freopen("uva11437.in","r",stdin); // freopen(".out","w",stdout); int T=read(); while(T--){ P A=read_point(),B=read_point(),C=read_point(); P p[3]={getP(A,B,C),getP(B,C,A),getP(C,A,B)}; printf("%0.lf\n",PolygonArea(p,3)); } return 0; }

UVA 11800 Determine the Shape 4边形判定

#include using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector #define pi pair #define SI(a) ((a).size()) typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } ll sqr(ll a){return a*a;} ld sqr(ld a){return a*a;} double sqr(double a){return a*a;} ld PI = 3.141592653589793238462643383; class P{ public: double x,y; P(double x=0,double y=0):x(x),y(y){} friend long double dis2(P A,P B){return sqr(A.x-B.x)+sqr(A.y-B.y); } friend long double Dot(P A,P B) {return A.x*B.x+A.y*B.y; } friend long double Length(P A) {return sqrt(Dot(A,A)); } friend long double Angle(P A,P B) {return acos(Dot(A,B) / Length(A) / Length(B) ); } friend P operator- (P A,P B) { return P(A.x-B.x,A.y-B.y); } friend P operator+ (P A,P B) { return P(A.x+B.x,A.y+B.y); } friend P operator* (P A,double p) { return P(A.x*p,A.y*p); } friend P operator/ (P A,double p) { return P(A.x/p,A.y/p); } friend bool operator< (const P& a,const P& b) {return a.xconst double eps=1e⑴0; int dcmp(double x) { if (fabs(x)return 0; else return x<0 ? -1 : 1; } bool operator==(const P& a,const P& b) { return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y) == 0; } typedef P V; double Cross(V A,V B) {return A.x*B.y - A.y*B.x;} double Area2(P A,P B,P C) {return Cross(B-A,C-A);} V Rotate(V A,double rad) { return V(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); } // A 不是 0向量 V Normal(V A) { double L = Length(A); return V(-A.y/L , A.x/L); } namespace complex_G{ typedef complex<double> Point; //real(p):实部 imag(p):虚部 conj(p):共轭 typedef Point Vector; double Dot(Vector A,Vector B) {return real(conj(A)*B); } double Cross(Vector A,Vector B) {return imag(conj(A)*B); } Vector Rotate(Vector A,double rad) {return A*exp(Point(0,rad)); } } //Cross(v,w)==0(平行)时,不能调这个函数 P GetLineIntersection(P p,V v,P Q,V w){ V u = p-Q; double t = Cross(w,u)/Cross(v,w); return p+v*t; } P GetLineIntersectionB(P p,V v,P Q,V w){ return GetLineIntersection(p,v-p,Q,w-Q); } double DistanceToLine(P p,P A,P B) { V v1 = B-A, v2 = p-A; return fabs(Cross(v1,v2))/Length(v1); } double DistanceToSegment(P p,P A,P B) { if (A==B) return Length(p-A); V v1 = B-A, v2 = p-A, v3 = p - B; if (dcmp(Dot(v1,v2))<0) return Length(v2); else if (dcmp(Dot(v1,v3))>0 ) return Length(v3); else return fabs(Cross(v1,v2) ) / Length(v1); } P GetLineProjection(P p,P A,P B) { V v=B-A; return A+v*(Dot(v,p-A)/Dot(v,v)); } //规范相交-线段相交且交点不在端点 bool SegmentProperIntersection(P a1,P a2,P b1,P b2) { double c1 = Cross(a2-a1,b1-a1) , c2 = Cross(a2-a1,b2-a1), c3 = Cross(b2-b1,a1-b1) , c4 = Cross(b2-b1,a2-b1); return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0; } //点在线段上（不包括端点） bool OnSegment(P p,P a1,P a2) { return dcmp(Cross(a1-p,a2-p)) == 0 && dcmp(Dot(a1-p,a2-p))<0; } double PolygonArea(P *p,int n) { double area=0; For(i,n-2) area+=Cross(p[i]-p[0],p[i+1]-p[0]); return area/2; } /*欧拉公式： V+F-E=2 V-点数 F面数 E边数 */ P read_point() { P a; scanf("%lf%lf",&a.x,&a.y); return a; } struct C{ P c; double r,x,y; C(P c,double r):c(c),r(r),x(c.x),y(c.y){} P point(double a) { return P(c.x+cos(a)*r,c.y+sin(a)*r); } }; struct Line{ P p; V v; double ang; Line(){} Line(P p,V v):p(p),v(v) {ang=atan2(v.y,v.x); } bool operator<(const Line & L) const { return angdouble a) { return p+v*a; } }; int getLineCircleIntersection(Line L,C cir,double &t1,double &t2,vector

& sol) { if (dcmp(DistanceToLine(cir.c,L.p,L.p+L.v)-cir.r)==0) { sol.pb(GetLineProjection(cir.c,L.p,L.p+L.v)); return 1; } double a = L.v.x, b = L.p.x - cir.c.x, c = L.v.y, d= L.p.y - cir.c.y; double e = a*a+c*c, f = 2*(a*b + c*d), g = b*b+d*d-cir.r*cir.r; double delta = f*f - 4*e*g; if (dcmp(delta)<0) return 0; else if (dcmp(delta)==0) { t1 = t2 = -f / (2*e); sol.pb(L.point(t1)); return 1; } t1 = (-f - sqrt(delta)) / (2*e); sol.pb(L.point(t1)); t2 = (-f + sqrt(delta)) / (2*e); sol.pb(L.point(t2)); return 2; } double angle(V v) {return atan2(v.y,v.x);} int getCircleCircleIntersection(C C1,C C2,vector

& sol) { double d = Length(C1.c-C2.c); if (dcmp(d)==0) { if (dcmp(C1.r - C2.r)==0) return -1; //2圆重合 return 0; } if (dcmp(C1.r+C2.r-d)<0) return 0; if (dcmp(fabs(C1.r-C2.r)-d)>0) return 0; double a = angle(C2.c-C1.c); double da = acos((C1.r*C1.r+d*d - C2.r*C2.r)/ (2*C1.r*d)); P p1 = C1.point(a-da), p2 = C1.point(a+da); sol.pb(p1); if (p1==p2) return 1; sol.pb(p2); return 2; } // Tangents-切线 int getTangents(P p,C c,V* v) { V u= c.c-p; double dist = Length(u); if (distreturn 0; else if (dcmp(dist-c.r)==0) { v[0]=Rotate(u,PI/2); return 1; } else { double ang = asin(c.r / dist); v[0]=Rotate(u,-ang); v[1]=Rotate(u,ang); return 2; } } //这个函数假定整数坐标和整数半径 //double时要把int改成double int getTangents(C A,C B,P* a,P* b) { int cnt=0; if (A.rint d2 = (A.c.x-B.c.x)*(A.c.x-B.c.x) + (A.c.y-B.c.y)*(A.c.y-B.c.y); int rdiff = A.r-B.r; int rsum = A.r+B.r; if (d2return 0; double base = atan2(B.y-A.y,B.x-A.x); if (d2==0 && A.r == B.r) return -1; if (d2 == rdiff*rdiff) { a[cnt] = A.point(base); b[cnt] = B.point(base); ++cnt; return 1; } double ang = acos((A.r-B.r)/sqrt(d2)); a[cnt] = A.point(base+ang); b[cnt] = B.point(base+ang); ++cnt; a[cnt] = A.point(base-ang); b[cnt] = B.point(base-ang); ++cnt; if (d2==rsum*rsum) { a[cnt] = A.point(base); b[cnt] = B.point(PI+base); ++cnt; } else if (d2>rsum*rsum) { double ang = acos((A.r+B.r)/sqrt(d2)); a[cnt] = A.point(base+ang); b[cnt] = B.point(PI+base+ang); ++cnt; a[cnt] = A.point(base-ang); b[cnt] = B.point(PI+base-ang); ++cnt; } return cnt; } //Circumscribed-外接 C CircumscribedCircle(P p1,P p2,P p3) { double Bx = p2.x-p1.x, By= p2.y-p1.y; double Cx = p3.x-p1.x, Cy= p3.y-p1.y; double D = 2*(Bx*Cy-By*Cx); double cx = (Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D + p1.x; double cy = (Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D + p1.y; P p =P(cx,cy); return C(p,Length(p1-p)); } //Inscribed-内接 C InscribedCircle(P p1,P p2,P p3) { double a = Length(p2-p3); double b = Length(p3-p1); double c = Length(p1-p2); P p = (p1*a+p2*b+p3*c)/(a+b+c); return C(p,DistanceToLine(p,p1,p2)); } double torad(double deg) { return deg/180*acos(-1); } //把 角度+-pi 转换到 [0,pi) 上 double radToPositive(double rad) { if (dcmp(rad)<0) rad=ceil(-rad/PI)*PI+rad; if (dcmp(rad-PI)>=0) rad-=floor(rad/PI)*PI; return rad; } double todeg(double rad) { return rad*180/acos(-1); } //(R,lat,lng)->(x,y,z) void get_coord(double R,double lat,double lng,double &x,double &y,double &z) { lat=torad(lat); lng=torad(lng); x=R*cos(lat)*cos(lng); y=R*cos(lat)*sin(lng); z=R*sin(lat); } void print(double a) { printf("%.6lf",a); } void print(P p) { printf("(%.6lf,%.6lf)",p.x,p.y); } template<class T> void print(vector v) { sort(v.begin(),v.end()); putchar('['); int n=v.size(); Rep(i,n) { print(v[i]); if (i1) putchar(','); } puts("]"); } // 把直线沿v平移 // Translation-平移 Line LineTranslation(Line l,V v) { l.p=l.p+v; return l; } void CircleThroughAPointAndTangentToALineWithRadius(P p,Line l,double r,vector

& sol) { V e=Normal(l.v); Line l1=LineTranslation(l,e*r),l2=LineTranslation(l,e*(-r)); double t1,t2; getLineCircleIntersection(l1,C(p,r),t1,t2,sol); getLineCircleIntersection(l2,C(p,r),t1,t2,sol); } void CircleTangentToTwoLinesWithRadius(Line l1,Line l2,double r,vector

& sol) { V e1=Normal(l1.v),e2=Normal(l2.v); Line L1[2]={LineTranslation(l1,e1*r),LineTranslation(l1,e1*(-r))}, L2[2]={LineTranslation(l2,e2*r),LineTranslation(l2,e2*(-r))}; Rep(i,2) Rep(j,2) sol.pb(GetLineIntersection(L1[i].p,L1[i].v,L2[j].p,L2[j].v)); } void CircleTangentToTwoDisjointCirclesWithRadius(C c1,C c2,double r,vector

& sol) { c1.r+=r; c2.r+=r; getCircleCircleIntersection(c1,c2,sol); } P p[4]; bool ConvexPolygon(P &A,P &B,P &C,P &D) { if (SegmentProperIntersection(A,C,B,D)) return 1; swap(B,C); if (SegmentProperIntersection(A,C,B,D)) return 1; swap(D,C); if (SegmentProperIntersection(A,C,B,D)) return 1; return 0; } bool IsParallel(P A,P B,P C,P D) { return dcmp(Cross(B-A,D-C))==0; } bool IsPerpendicular(V A,V B) { return dcmp(Dot(A,B))==0; } //先调用ConvexPolygon 求凸包并确认是不是是4边形 // Trapezium-梯形 Rhombus-菱形 bool IsTrapezium(P A,P B,P C,P D){ return IsParallel(A,B,C,D)^IsParallel(B,C,A,D); } bool IsParallelogram(P A,P B,P C,P D) { return IsParallel(A,B,C,D)&&IsParallel(B,C,A,D); } bool IsRhombus(P A,P B,P C,P D) { return IsParallelogram(A,B,C,D)&&dcmp(Length(B-A)-Length(C-B))==0; } bool IsRectangle(P A,P B,P C,P D) { return IsParallelogram(A,B,C,D)&&IsPerpendicular(B-A,D-A); } bool IsSquare(P A,P B,P C,P D) { return IsParallelogram(A,B,C,D)&&IsPerpendicular(B-A,D-A)&&dcmp(Length(B-A)-Length(C-B))==0; } int main() { // freopen("uva11800.in","r",stdin); // freopen(".out","w",stdout); int T=read(); For(kcase,T) { Rep(i,4) p[i]=read_point(); cout<<"Case "<": "; if (!ConvexPolygon(p[0],p[1],p[2],p[3])) puts("Ordinary Quadrilateral"); else { P A=p[0],B=p[1],C=p[2],D=p[3]; if (IsSquare(A,B,C,D)) puts("Square"); else if (IsRectangle(A,B,C,D)) puts("Rectangle"); else if (IsRhombus(A,B,C,D)) puts("Rhombus"); else if (IsParallelogram(A,B,C,D)) puts("Parallelogram"); else if (IsTrapezium(A,B,C,D)) puts("Trapezium"); else puts("Ordinary Quadrilateral"); } } return 0; }

UVA 11646 Athletics Track

#include using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector #define pi pair #define SI(a) ((a).size()) typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int main() { // freopen("uva11646.in","r",stdin); // freopen(".out","w",stdout); double a,b; int kcase=1; while(scanf("%lf : %lf\n",&a,&b)!=EOF) { double r=sqrt(a*a+b*b)/2; double xita=asin(b/2.0/r)*2; double rxita=r*xita; double x=200.0/(a +rxita); printf("Case %d: %.10lf %.10lf\n",kcase++,a*x,b*x); } return 0; }

UVA 11817 Tunnelling the Earth 球面距离

#include using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector #define pi pair #define SI(a) ((a).size()) typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } ll sqr(ll a){return a*a;} ld sqr(ld a){return a*a;} double sqr(double a){return a*a;} ld PI = 3.141592653589793238462643383; class P{ public: double x,y; P(double x=0,double y=0):x(x),y(y){} friend long double dis2(P A,P B){return sqr(A.x-B.x)+sqr(A.y-B.y); } friend long double Dot(P A,P B) {return A.x*B.x+A.y*B.y; } friend long double Length(P A) {return sqrt(Dot(A,A)); } friend long double Angle(P A,P B) {return acos(Dot(A,B) / Length(A) / Length(B) ); } friend P operator- (P A,P B) { return P(A.x-B.x,A.y-B.y); } friend P operator+ (P A,P B) { return P(A.x+B.x,A.y+B.y); } friend P operator* (P A,double p) { return P(A.x*p,A.y*p); } friend P operator/ (P A,double p) { return P(A.x/p,A.y/p); } friend bool operator< (const P& a,const P& b) {return a.x
------分隔线----------------------------

上一篇 【Leetcode】Largest Divisible Subset

下一篇 android-----事件分发机制测试系列

------分隔线----------------------------

最新技术推荐

1Java并发编程的艺术(六)——线程间的通信 2Java并发编程的艺术(三)——volatile 3Node核心模块之Events 4myeclipse源码相关操作 5springMVC源码分析--RequestParamMethodArgumentResolver参数解析器（三） 6Java基本数据类型总结 7java结合testng，利用XML做数据源的数据驱动示例