/*******************************************************/
平面几何
点，线，面，形基本关系，点积叉积的理解
POJ 2318 TOYS（推荐）
思路：根据差积可知：P x Q>0,P在Q的顺时针方向；P x Q<0,P在Q的逆时针方向；P x Q=0,P与Q共线，同向或反向。。所以如果一个点在一个四边形内，则与两对边的差积小于0.。。。。。。。。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2318
/************************************************************** Problem:poj 2318 User: youmi Language: C++ Result: Accepted Time:922MS Memory:852K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define eps 1e-8 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; const double PI=acos(-1.0); int n,m; const int maxn=5000+10; int sgn(double x) { if(fabs(x)<eps) return 0; if(x<0) return -1; else return 1; } struct Point { double x,y; Point(){}; Point(double _x,double _y) { x=_x,y=_y; } Point operator- (const Point &_b)const { return Point(x-_b.x,y-_b.y); } double operator*(const Point &_b)const { return x*_b.x+y*_b.y; } double operator^(const Point &_b)const { return x*_b.y-y*_b.x; } void transXY(double _B) { double tx=x,ty=y; x=tx*cos(_B)-ty*sin(_B); y=tx*sin(_B)+ty*cos(_B); } }; double cross(struct Point _s,struct Point _e1,struct Point _e2) { Point s,e; s=Point(_e1.x-_s.x,_e1.y-_s.y); e=Point(_e2.x-_s.x,_e2.y-_s.y); return s^e; } Point p[maxn],q[maxn]; int cnt[maxn]; void sovle(struct Point cur) { for(int i=1;i<=n;i++) { if(sgn(cross(p[i],q[i],cur)*cross(p[i-1],q[i-1],cur))==-1) { cnt[i-1]++; return; } } } int main() { //freopen("in.txt","r",stdin); int kase=0; while(~sc(n)&&n) { if(kase++) cout<<endl; sc(m); int x1,y1,x2,y2; sc2(x1,y1); p[0].x=x1,p[0].y=0; q[0].x=x1,q[0].y=y1; sc2(x2,y2); p[n+1]=Point(x2,y2); q[n+1]=Point(x2,y1); rep1(i,n) { sc2(x1,x2); p[i]=Point(x2,y2); q[i]=Point(x1,y1); } ++n; /**< for(int i=0;i<=n;i++) { printf("%.0f %.0f %.0f %.0f ",p[i].x,p[i].y,q[i].x,q[i].y); } */ zeros(cnt); Point cur; rep1(i,m) { scanf("%lf%lf",&cur.x,&cur.y); sovle(cur); } for(int i=0;i<n;i++) printf("%d: %d ",i,cnt[i]); } return 0; }
poj 3304 Segments http://poj.org/problem?id=3304
思路：http://blog.csdn.net/heartnheart/article/details/5924116 （坑点：n==1的时候）
/************************************************************** Problem:poj 3304 User: youmi Language: C++ Result: Accepted Time:79MS Memory:680K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-8 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; const double pi=acos(-1.0); int sgn(double x) { if(fabs(x)<esp) return 0; if(x<0) return -1; else return 1; } typedef struct Point { double x,y; Point(){}; Point(double _x,double _y) { x=_x,y=_y; } bool operator==(const Point&_B)const { return sgn(x-_B.x)==0&&sgn(y-_B.y)==0; } bool operator!=(const Point&_B)const { return sgn(x-_B.x)!=0||sgn(y-_B.y)!=0; } Point operator-(const Point&_b)const { return Point(x-_b.x,y-_b.y); } double operator*(const Point&_b)const { return x*_b.x+y*_b.y; } double operator^(const Point&_b)const { return x*_b.y-y*_b.x; } void transXY(double _B) { double tx=x,ty=y; x=tx*cos(_B)-ty*sin(_B); y=tx*sin(_B)+ty*cos(_B); } }point; typedef struct Line { Point s,e; Line(){}; Line(Point _s,Point _e) { s=_s,e=_e; } pair<int,Point>operator&(const Line &_B)const { Point res=s; if(sgn((s-e)^(_B.s-_B.e))==0) { if(sgn((s-_B.e)^(_B.s-_B.e))==0) return make_pair(0,res); else return make_pair(1,res); } double t=((s-_B.s)^(_B.s-_B.e))/((s-e)^(_B.s-_B.e)); res.x+=(e.x-s.x)*t; res.y+=(e.y-s.y)*t; return make_pair(2,res); } }line; double dist(Point a,Point b) { return sqrt((a-b)*(a-b)); } bool inter(line l1,line l2) { return Max(l1.s.x,l1.e.x)>=Min(l2.s.x,l2.e.x)&& Max(l2.s.x,l2.e.x)>=Min(l1.s.x,l1.e.x)&& Max(l1.s.y,l1.e.y)>=Min(l2.s.y,l2.e.y)&& Max(l2.s.y,l2.e.y)>=Min(l1.s.y,l1.e.y)&& sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0&& sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0; } bool Seg_inter_line(line l1,line l2) { return sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0; } int n; const int maxn=110; line seg[maxn]; bool solve(line cur) { rep1(k,n) { if(!Seg_inter_line(cur,seg[k])) return false; } return true; } int main() { //freopen("in.txt","r",stdin); int T_T; scanf("%d",&T_T); for(int kase=1;kase<=T_T;kase++)/**< */ { sc(n); double x1,y1,x2,y2; rep1(i,n) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); seg[i]=Line(Point(x1,y1),Point(x2,y2)); } if(n<=2) { printf("Yes! "); continue; } int flag=0; rep1(i,n) { rep1(j,n) { if(i!=j) { line cur; if((seg[i].s!=seg[j].s)) { cur=Line(seg[i].s,seg[j].s); if(solve(cur)) { flag=1; break; } } if((seg[i].s!=seg[j].e)) { cur=Line(seg[i].s,seg[j].e); if(solve(cur)) { flag=1; break; } } if((seg[i].e!=seg[j].s)) { cur=Line(seg[i].e,seg[j].s); if(solve(cur)) { flag=1; break; } } if((seg[i].e!=seg[j].e)) { cur=Line(seg[i].e,seg[j].e); if(solve(cur)) { flag=1; break; } } } } if(flag==1) break; } puts(flag?"Yes!":"No!"); } return 0; }
poj 1556 The Doors http://poj.org/problem?id=1556
思路：因为最多18行，所以最多4*18+2个点，在100量级的点求最短路，想怎么求就怎么求，只不多在更新的时候加上交叉判断就好了，不交叉跟新就好啦、、、。。。这题能够1A还得感谢神队友教我调试方法，太好使了。。。。。。。。。。。。。。。。！！！！！！！！！！！！！！！！！！！
/************************************************************** Problem:poj 1556 User: youmi Language: C++ Result: Accepted Time:0MS Memory:700K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-8 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; int n; const int maxn=100; double dis[maxn]; const int PI=acos(-1.0); int sgn(double x) { if(fabs(x)<esp) return 0; if(x<0) return -1; else return 1; } typedef struct Point { double x,y; Point(){}; Point(double _x,double _y) { x=_x,y=_y; } Point operator-(const Point & _b)const { return Point(x-_b.x,y-_b.y); } double operator *(const Point &_b)const { return x* _b.x+y* _b.y; } double operator^(const Point &_b)const { return x* _b.y- _b.x*y; } void transXY(double _b) { double tx=x,ty=y; x=tx*cos(_b)-ty*sin(_b); y=tx*sin(_b)+ty*cos(_b); } }point; point st=Point(0,5),ed=Point(10,5); point mat[25][10]; typedef struct Line { point s,e; Line(){}; Line(point _s,point _e) { s=_s,e=_e; } }line; line ln[25][10]; double dist(point a,point b) { return sqrt((a-b)*(a-b)); } bool inter(line l1,line l2) { return Max(l1.s.x,l1.e.x)>=Min(l2.s.x,l2.e.x)&& Max(l1.s.y,l1.e.y)>=Min(l2.s.y,l2.e.y)&& Max(l2.s.x,l2.e.x)>=Min(l1.s.x,l1.e.x)&& Max(l2.s.y,l2.e.y)>=Min(l1.s.y,l1.e.y)&& sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0&& sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0; } bool is_inter(line temp,int l,int r) { for(int i=l;i<=r;i++) { for(int j=1;j<=3;j++) { if(inter(temp,ln[i][j])) return true; } } return false; } bool vis[maxn]; void solve() { int tot=n*4; line temp; for(int i=1;i<=n;i++) { for(int j=1;j<=4;j++) { temp=Line(st,mat[i][j]); int now=(i-1)*4+j-1; if(is_inter(temp,1,i-1)) dis[now]=oo; else dis[now]=dist(st,mat[i][j]); } } if(is_inter(Line(st,ed),1,n)) dis[tot]=oo; else dis[tot]=dist(st,ed); zeros(vis); int cnt=0,now,u; while(cnt<=tot) { now=oo; for(int i=0;i<=tot;i++) { if(!vis[i]&&now>dis[i]) { now=dis[i]; u=i; } } vis[u]=1; for(int i=0;i<=tot;i++) { temp=Line(mat[u/4+1][u%4+1],mat[i/4+1][i%4+1]); int mn=Min(i,u); int mx=Max(i,u); double len=dist(mat[u/4+1][u%4+1],mat[i/4+1][i%4+1]); if(i!=u&&!is_inter(temp,mn/4+2,mx/4)&&dis[i]>dis[u]+len) dis[i]=dis[u]+len; } cnt++; } printf("%.2f ",dis[tot]); } int main() { //freopen("in.txt","r",stdin); while(~sc(n)&&~n) { double x0,y0; rep1(i,n) { scanf("%lf",&x0); mat[i][0]=Point(x0,0),mat[i][5]=Point(x0,10); rep1(j,4) { scanf("%lf",&y0); mat[i][j]=Point(x0,y0); } ln[i][1]=Line(mat[i][0],mat[i][1]),ln[i][2]=Line(mat[i][2],mat[i][3]),ln[i][3]=Line(mat[i][4],mat[i][5]); } mat[n+1][1]=ed; solve(); } return 0; }
poj 1113 Wall http://poj.org/problem?id=1113
思路：基础的凸包问题，结果就是周长加上2*pi*L。。。。。。。话说自从学会精湛的调试方法后一路1A。。。。。。。。。。
/************************************************************** Problem:poj 1113 User: youmi Language: C++ Result: Accepted Time:63MS Memory:692K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; int n,len; const double PI=acos(-1.0); const int maxn=1000+10; int sgn(double x) { if(fabs(x)<esp) return 0; if(x<0) return -1; else return 1; } struct point { double x,y; point(){}; point(double _x,double _y) { x=_x,y=_y; } point operator-(const point &_b)const { return point(x-_b.x,y-_b.y); } double operator *(const point &_b)const { return x*_b.x+y*_b.y; } double operator^(const point &_b)const { return x*_b.y-_b.x*y; } }; double dist(point a,point b) { return sqrt((a-b)*(a-b)); } point lst[maxn]; int stc[maxn],top; bool _cmp(point p1,point p2) { double temp=(p1-lst[0])^(p2-lst[0]); if(sgn(temp)>0) return true; else if(sgn(temp)==0&&sgn(dist(p1,lst[0])-dist(p2,lst[0]))<=0) return true; else return false; } void graham() { point p0=lst[0]; int k=0; for(int i=1;i<n;i++) { if((p0.y>lst[i].y)||(p0.y==lst[i].y&&p0.x>lst[i].x)) { p0=lst[i]; k=i; } } swap(lst[k],lst[0]); sort(lst+1,lst+n,_cmp); if(n==1) { top=1; stc[0]=0; return ; } top=2; stc[0]=0; stc[1]=1; if(n==2) return ; for(int i=2;i<n;i++) { while(top>1&&sgn((lst[stc[top-1]]-lst[stc[top-2]])^(lst[i]-lst[stc[top-2]]))<=0) top--; stc[top++]=i; } } int main() { //freopen("in.txt","r",stdin); while(~sc2(n,len)) { double x0,y0; rep0(i,n) { scanf("%lf%lf",&x0,&y0); lst[i]=point(x0,y0); } graham(); if(n<=2) { printf("0 "); continue; } double ans=0; for(int i=0;i<top;i++) { point a=lst[stc[(i-1+top)%top]]; point b=lst[stc[(i-0+top)%top]]; ans+=dist(a,b); } ans+=2*PI*len; ll temp=(ll)floor(ans); if((int)fabs(ans-temp+0.5)==1) printf("%lld ",temp+1); else printf("%lld ",temp); } return 0; }
/*******************************************************/
立体几何
题目链接：hdu 5733 tetrahedron
题意：给定一个四面体，求其内切圆半径和内心，如若不存在输出4个‘O’。
解题： 首先用叉积判断是否四点共面，若四点共面，则不能形成四面体。随后，利用四面体体积公式，海伦公式（求三角形面积），四面体内心公式，求出四面 体的内切圆半径和内心。
/************************************************************** Problem:hdu 5733 User: youmi Language: C++ Result: Accepted Time:0MS Memory:1616K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep(i,from,to) for(int i=from;i<=to;i++) #define irep(i,to,from) for(int i=to;i>=from;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define eps 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl const double pi=4*atan(1.0); using namespace std; typedef long long ll; template <class T> inline void read(T &n) { char c; int flag = 1; for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag; } int Pow(int base, ll n, int mo) { if (n == 0) return 1; if (n == 1) return base % mo; int tmp = Pow(base, n >> 1, mo); tmp = (ll)tmp * tmp % mo; if (n & 1) tmp = (ll)tmp * base % mo; return tmp; } inline int sign(double p) { if(p>eps)return 1; else if(p<-eps)return -1; else return 0; } struct Point { double x,y,z; Point(double xx=0,double yy=0,double zz=0):x(xx),y(yy),z(zz){} Point operator +(const Point p1) { return Point(x+p1.x,y+p1.y,z+p1.z); } Point operator -(const Point p1) { return Point(x-p1.x,y-p1.y,z-p1.z); } Point operator *(const Point p1) { return Point(y*p1.z-z*p1.y,z*p1.x-x*p1.z,x*p1.y-y*p1.x); } Point operator *(double d) { return Point(d*x,d*y,d*z); } Point operator /(double d) { return Point(x/d,y/d,z/d); } double operator ^(const Point p1) { return x*p1.x+y*p1.y+z*p1.z; } double getLen() { return sqrt(x*x+y*y+z*z); } int read() { return scanf("%lf%lf%lf",&x,&y,&z); } }; struct Plane { Point a,b,c; Plane(){} Plane(Point _a,Point _b,Point _c):a(_a),b(_b),c(_c){} }; struct CH3D { double vlen(Point a) { return sqrt(a.x*a.x+a.y*a.y+a.z*a.z); } Point normal_vec(Plane s) { return (s.a-s.b)*(s.b-s.c); } Point cross(Point a,Point b,Point c) { return Point( (b.y-a.y)*(c.z-a.z)-(b.z-a.z)*(c.y-a.y), (b.z-a.z)*(c.x-a.x)-(b.x-a.x)*(c.z-a.z), (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x) ); } //三角形面积 double area(Point a,Point b,Point c) { return fabs(vlen((b-a)*(c-a))/2.0); } //四面体面积 double volume(Point a,Point b,Point c,Point d) { return fabs(((b-a)*(c-a))^(d-a)/6.0); } }; //*************************** CH3D hull; int n; Point a,b,c,d; void work() { double v=hull.volume(a,b,c,d); double s1=hull.area(a,b,c); double s2=hull.area(a,b,d); double s3=hull.area(b,c,d); double s4=hull.area(a,c,d); double r=3*v/(s1+s2+s3+s4); double sum=s1+s2+s3+s4; double x1=(s1*d.x+s2*c.x+s3*a.x+s4*b.x)/sum; double y1=(s1*d.y+s2*c.y+s3*a.y+s4*b.y)/sum; double z1=(s1*d.z+s2*c.z+s3*a.z+s4*b.z)/sum; printf("%.4lf %.4lf %.4lf %.4lf ",x1,y1,z1,r); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif while(~a.read()) { b.read(); c.read(); d.read(); Plane s=Plane(a,b,c); if(fabs(hull.normal_vec(s)^(d-a))<eps) { printf("O O O O "); continue; } work(); } }