二维向量旋转
知识点参考： http://www.cnblogs.com/woodfish1988/archive/2007/09/10/888439.html
x1= x * cos(θ) - y * sin(θ)
y1= x * sin(θ) + y *cos(θ)
求平面上任意点 绕任意点p(x,y)旋转 角度 sita 后的坐标矩阵
hdu 1700 Points on Cycle
题意：已知圆上一点， 求另外两点， 使得三角形周长最大， 则该三角形为等边三角形， 直接将 一点 顺时和 逆时针 旋转120 得到另外两点， 即可。
代码如下：
using namespace std ;const double pi= acos(-1);#define arc(x) (x / 180 * pi)typedef long long LL ;const double EPS = 0.0005;struct Point { double x,y; Point(){} Point(double x, double y):x(x),y(y){} Point rot( double sita){ return Point( x * cos(sita) - y*sin(sita) , x* sin(sita) + y * cos(sita) ); }};int main(){ int t; scanf("%d",&t); Point p0, p1, p2; while(t--){ scanf("%lf%lf",&p0.x,&p0.y); p1=p0.rot( arc(120.0) ); p2=p0.rot( arc(-120.0) ); if( p1.y - p2.y > EPS ) swap(p1,p2); else if( (fabs(p1.y - p2.y) < EPS) && (p1.x - p2.x > EPS) ) swap(p1,p2); printf("%.3lf %.3lf %.3lf %.3lf\n",p1.x, p1.y, p2.x, p2.y); } return 0;}
hdu 1033 Edge
题目来源： http://acm.hdu.edu.cn/showproblem.php?pid=1033
分析：求点绕任意点（x,y）旋转角度90（-90）后的坐标。
模板题
double mat[3][3];// 绕任一点（x，y）旋转角度sita 其中 c = cos(sita) s = sin(sita)void Get_mat(double c, double s, double x, double y){ mat[0][0] = c; mat[0][1] = -s ; mat[0][2] = (1 - c) * x + s * y ; mat[1][0] = s; mat[1][1] = c ; mat[1][2] = (1 - c) * y - s * x; mat[2][0] = mat[2][1] = 0; mat[2][2] = 1;}
代码如下：
using namespace std ;const double pi= acos(-1.0);#define arc(x) (x / 180 * pi)const double EPS = 1e-8;const int Max_N = 35;double mat[3][3];// 绕过原点和（x，y，z）的轴，转 a 角度的 旋转矩阵，注意传的点向量为单位向量，a为弧度void Get_mat(double c, double s, double x, double y){ mat[0][0] = c; mat[0][1] = -s ; mat[0][2] = (1 - c) * x + s * y ; mat[1][0] = s; mat[1][1] = c ; mat[1][2] = (1 - c) * y - s * x; mat[2][0] = mat[2][1] = 0; mat[2][2] = 1;}int main(){ string s; int st[3],ed[3],tmp[3]; while(cin>>s){ st[0] = 300, st[1] = 420, st[2] = 1 ; ed[0] = 310, ed[1] = 420, ed[2] = 1 ; int len=s.length(); printf("300 420 moveto\n310 420 lineto\n"); for(int i=0; i
三维向量旋转。
左手坐标系下，一点绕任意轴旋转θ角的右乘矩阵：
其中C为cosθ，S为sinθ，A为单位化的旋转轴。
推导过程 请 参照 http://blog.csdn.net/tan625747/article/details/5523728
hdu 2898 旋转
题目来源： http://acm.hdu.edu.cn/showproblem.php?pid=2898
求空间中一个点绕一穿过原点的轴线旋转一定角度后的坐标，沿着旋转轴往原点看旋转的角度为顺时针。
沿着旋转轴往原点看旋转的角度为顺时针，模板
double mat[3][3];// 绕过原点和（x，y，z）的轴，转 a 角度的 旋转矩阵，注意传的点向量为单位向量，a为弧度void Get_mat(double x,double y,double z, double a){ double c=cos(a); double s=sin(a); double xy = x*y, xz = x*z, yz = y*z, xx = x*x, yy = y*y , zz = z*z ; mat[0][0] = xx + (1 - xx) * c; mat[0][1] = xy * (1-c) - z * s; mat[0][2] = xz * (1-c) + y * s; mat[1][0] = xy * (1 - c) + z * s; mat[1][1] = yy + (1 - yy) * c; mat[1][2] = yz * (1-c) -x * s ; mat[2][0] = xz * (1 - c) - y * s; mat[2][1] = yz * (1-c) + x * s; mat[2][2] = zz + (1 - zz) * c;}
代码如下：
using namespace std ;const double pi= acos(-1);#define arc(x) (x / 180 * pi)const double EPS = 1e-8;const int Max_N = 35;double mat[3][3];// 绕过原点和（x，y，z）的轴，转 a 角度的 旋转矩阵，注意传的点向量为单位向量，a为弧度void Get_mat(double x,double y,double z, double a){ double c=cos(a); double s=sin(a); double xy = x*y, xz = x*z, yz = y*z, xx = x*x, yy = y*y , zz = z*z ; mat[0][0] = xx + (1 - xx) * c; mat[0][1] = xy * (1-c) - z * s; mat[0][2] = xz * (1-c) + y * s; mat[1][0] = xy * (1 - c) + z * s; mat[1][1] = yy + (1 - yy) * c; mat[1][2] = yz * (1-c) -x * s ; mat[2][0] = xz * (1 - c) - y * s; mat[2][1] = yz * (1-c) + x * s; mat[2][2] = zz + (1 - zz) * c;}int main(){ double px[3]; double py[3]; double x,y,z; double a; while(scanf("%lf%lf%lf", &px[0], &px[1], &px[2] ) != EOF){ memset(py,0,sizeof(py)); scanf("%lf%lf%lf%lf",&x,&y, &z, &a); double len = sqrt(x * x + y * y +z *z) ; Get_mat(x / len, y / len, z / len, a); for(int i=0; i<3; i++){ for(int j=0; j<3; j++){ py[i] += mat[i][j]*px[j]; } } printf("%.3lf %.3lf %.3lf\n",py[0],py[1],py[2]); } return 0;}
hit Cubic Rotation
题目来源： http://acm.hrbeu.edu.cn/index.php?act=problem&id=1006&cid=16
The ACM/ICPC Asia Harbin Online First Round Contest 2010
分析： 求 正方体 绕 任意轴 p1p2 向量， 旋转 sita 角度后 ， 在 平面 xoy 平面上的 投影面积。 （旋转 + 凸包面积）。
由于是 任意轴 ，故在 代入 旋转公式前， 先平移（-p1）向量， 再 代入旋转公式， 再 逆平移（p1）;
注意， 题中 案例 2 ，中的 275 应改成 270， 这题 做了 ，显然 却不能提交。
代码如下：
using namespace std ;const double pi= acos(-1.0);#define arc(x) (x / 180 * pi)const double EPS = 1e-8;double mat[3][3];// 绕过原点和（x,y,z ）的轴，转a 角度的旋转矩阵，注意传入的点向量为单位向量， a 为弧度void Get_mat(double x, double y, double z, double a){ double c = cos(a); double s = sin(a); double xy = x*y, xz = x*z, yz = y*z, xx = x*x, yy = y*y, zz = z*z; mat[0][0] = xx + (1-xx)* c; mat[0][1] = xy * (1 - c) - z* s; mat[0][2] = xz * (1 - c) + y * s; mat[1][0] = xy * (1 - c) + z * s; mat[1][1] = yy + (1 - yy) *c; mat[1][2] = yz * (1- c) - x * s; mat[2][0] = xz * (1 - c) - y * s; mat[2][1] = yz * (1 - c) + x * s; mat[2][2] = zz + (1 - zz) * c;}int len ;double dir[8][3] = { { 0, 0 ,0}, { 1, 0, 0}, { 1, 0, 1}, { 0, 0, 1}, { 0, 1, 0}, { 1, 1, 0}, { 1, 1, 1}, { 0, 1, 1}};struct Point{ double x,y,z; Point(){} Point(double x, double y, double z):x(x),y(y),z(z){} Point operator + (Point p){ return Point( x + p.x , y + p.y, z + p.z); } Point operator - (Point p){ return Point( x - p.x , y - p.y, z - p.z); }};Point cub[10],p1,p2,tmp[10];// 求凸包以及凸包形成的面积double add(double a, double b){ if(fabs(a+b) < EPS * (fabs(a) + fabs(b)) ) return 0; return a+b;}struct tubao{ double x,y; tubao(){} tubao(double x, double y):x(x),y(y){} double operator ^(tubao p){ return add(x*p.y ,-y*p.x ); }};//p0p1 * p0p2 > 0 左转double xmult(tubao p1, tubao p2, tubao p0){ return add( (p1.x-p0.x)*(p2.y-p0.y), -(p1.y-p0.y)*(p2.x-p0.x) );}tubao List[10];int top;tubao qs[10];bool operator < (tubao a, tubao b){ if(a.y != b.y) return a.y < b.y; else return a.x < b.x;}double graham(int n){ sort(List, List + n); double sum=0; if(n == 0 || n == 1) return 0; qs[0] = List[0]; qs[1] = List[1]; top =1; for(int i=2; i = 1 && xmult(qs[top], List[i] , qs[top - 1]) <= 0) top --; qs[++top] = List[i]; } qs[++top] = List[n-2]; int le = top; for(int i=n-3; i>= 0; i--){ while(top >= le && xmult(qs[top], List[i], qs[top - 1]) <= 0) top--; qs[++top] = List[i]; } for(int i=0; i
2014年携程决赛 飞机的碎片
题目来源： http://acm.hdu.edu.cn/diy/contest_showproblem.php?cid=23086&pid=1002
Problem Description
一架飞机不幸在某海洋上失事，海面上漂浮着一架飞机的一些碎片…… 幸好有卫星把这些碎片拍下来了，可以大致让我们确定一块搜索的区域来确定失事飞机的位置。 为了更好地进行搜救，节约成本，需要在海上划出一块周长尽可能小的区域进行巡逻式的搜救。但是由于技术问题，巡逻的区域只能是矩形。现给出这些碎片的相对位置，请告知这块巡逻区域的周长（请务必保留小数点后6位数字） 由于雷达扫描到的碎片相对于广阔的海洋实在太小，可以用极小的点来代替它。
Input
输入包含多组测试用例，每组测试用例的第一行包含一个整数N(3≤N≤10 000)，表示碎片在海洋里的数量，接下去N行中的每行都有两个整数Xi和Yi（0 ≤ Xi, Yi ≤ 10 000），表示碎片的坐标。每个碎片的坐标都不同，并且所有的碎片都不在同一直线上。
Output
每一个测试用例，输出一行包含一个实数，一个矩形区域的最小周长。注意矩形的边缘不需要与坐标轴平行。
Sample Input
30 01 00 1
Sample Output
4.000000
Source
CodingTrip - 携程编程大赛 （决赛）
分析：
1： 最小包围盒。 题意是求把所有点包含在内的最小矩阵的周长。
2：我们先求所有点构成的凸包， 最小矩阵一定过凸包的某一条边。 如果边 平行于 x轴， 取 最左边点和最右边点 和 y轴方向最远的点， 如果 边 平行于 y 轴， 取 最上和最下的点 和 x轴最远的点， 如果 边 不平行于 轴， 则 对 凸包进行旋转，（平面上绕任意点 进行的旋转矩阵） 使边 平行于 x 轴， 进行同样的处理。求最小值。
代码如下：
const double pi= acos(-1.0);#define arc(x) (x / 180 * pi)const double EPS = 1e-8;const int Max_N = 10005;const double inf = 0xfffffff;// 求凸包以及凸包形成的面积double add(double a, double b){ if(fabs(a+b) < EPS * (fabs(a) + fabs(b)) ) return 0; return a+b;}struct Point{ double x,y; Point(){} Point(double x, double y):x(x),y(y){} double operator ^(Point p){ return add(x*p.y ,-y*p.x ); } double dist(Point p){ return sqrt( add( (x- p.x)*(x - p.x) ,(y - p.y)*(y - p.y) ) ) ; }};//p0p1 * p0p2 > 0 左转double xmult(Point p1, Point p2, Point p0){ return add( (p1.x-p0.x)*(p2.y-p0.y), -(p1.y-p0.y)*(p2.x-p0.x) );}Point List[Max_N];int top,n;Point qs[Max_N];Point tmp[Max_N];bool operator < (Point a, Point b){ if(a.y != b.y) return a.y < b.y; else return a.x < b.x;}double graham(){ // qs[0] = qs[top] = 原点。 sort(List, List + n); if(n == 0 || n == 1) return 0; qs[0] = List[0]; qs[1] = List[1]; top =1; for(int i=2; i = 1 && xmult(qs[top], List[i] , qs[top - 1]) <= 0) top --; qs[++top] = List[i]; } qs[++top] = List[n-2]; int le = top; for(int i=n-3; i>= 0; i--){ while(top >= le && xmult(qs[top], List[i], qs[top - 1]) <= 0) top--; qs[++top] = List[i]; }}// 平面上 绕 任意点 逆时针旋转 角度 sita(弧度) 矩阵double mat[3][3];void Get_mat(double x, double y , double sita){ double c = cos(sita); double s = sin(sita); mat[0][0] = c; mat[0][1] = -s; mat[0][2] = (1 - c) * x + s * y ; mat[1][0] = s; mat[1][1] = c; mat[1][2] = (1 - c) * y - s * x; mat[2][0] =mat[2][1] = 0; mat[2][2] = 1; }int main(){ while(scanf("%d",&n) != EOF){ int i,k,j,h; double changy,kuanx; double Min = inf; for(i=0; i qs[j].y ? k : j; changy = qs[k].y - qs[0].y; k=i; for( j = 0; j fabs(qs[k].x - qs[i].x) ? j : k; kuanx = fabs( qs[k].x - qs[i].x ) ; Min = min(2*(changy + kuanx), Min ); continue; } else if(qs[i].y == qs[i+1].y){ // 最小的x， 最大的x for(h=k=j=0; j qs[j].x ? k : j ; h = qs[h].x < qs[j].x ? h : j ; } kuanx = qs[k].x - qs[h].x ; //距离最大的y 纵距 for(k=j =0 ; j fabs(qs[k].y - qs[i].y) ? j : k; changy = fabs( qs[k].y - qs[i].y ) ; Min = min(2*(changy + kuanx), Min ); continue; } else { double sita = -atan2 ( (qs[i+1].y - qs[i].y) , (qs[i+1].x -qs[i].x ) ); double sss=sita / pi * 180; Get_mat(qs[i].x , qs[i].y , sita); for(j=0; j tmp[j].x ? k : j ; h = tmp[h].x < tmp[j].x ? h : j ; } kuanx = tmp[k].x - tmp[h].x ; //距离最大的y 纵距 for(k=j =0 ; j fabs(tmp[k].y - tmp[i].y) ? j : k; changy = fabs( tmp[k].y - tmp[i].y ) ; Min = min(2*(changy + kuanx), Min ); continue; } } printf("%.6lf\n", Min); } return 0;}