![]()
//
// main.cpp
// multi2016.1.G
//
// Created by New_Life on 16/7/27.
// Copyright © 2016年 chenhuan001. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define MOD 1000000007
typedef long long ll;
ll save[1100];
ll save1[11][11];
ll pow2[11];
ll mark[1<<10][1<<10][10][2];
ll dfs(int L,int R,int flag,ll cnt)
{
if(mark[L][R][cnt][flag]!=-1) return mark[L][R][cnt][flag];
if(L==0 && R==0) return 1;
if(L==0) return mark[L][R][cnt][flag]=save1[save[R]][cnt];
if(R==0) return mark[L][R][cnt][flag]=save1[save[L]][cnt];
ll tcnt = 0;
if(flag == 0)//左边选择
{
int tr = R;
for(;tr!=0;tr = ((tr-1)&R) )//必定选择一个以上
{
tcnt += save1[ save[tr] ][cnt]*dfs(L, R-tr, flag^1, save[tr]);
tcnt %= MOD;
}
}
else//右边选择
{
int tl = L;
for(;tl!=0;tl = ((tl-1)&L) )//必定选择一个以上
{
tcnt += save1[ save[tl] ][cnt]*dfs(L-tl, R, flag^1, save[tl]);
tcnt %= MOD;
}
}
return mark[L][R][cnt][flag]=tcnt;
}
ll C[12][12];
void get_C()
{
C[0][0] = 1;
for(int i=1;i<=10;i++)
{
C[i][0] = 1;
for(int j=1;j<=i;j++)
C[i][j] = C[i-1][j]+C[i-1][j-1];
}
}
void get_fff()
{
for(int n=1;n<=10;n++)
for(int m=1;m<=10;m++)
{
ll add[110];
for(int j=1;j<=m;j++) add[j] = C[m][j];
ll tmp[2][110];
memset(tmp,0,sizeof(tmp));
int a = 0;
tmp[a][0] = 1;
for(int i=1;i<=n;i++)
{
memset(tmp[a^1],0,sizeof(tmp[a^1]));
for(int j=100;j>=1;j--)
{
for(int k=1;k<=m;k++)
{
if(j-k < 0) continue;
tmp[a^1][j] = (tmp[a^1][j] + tmp[a][j-k]*add[k])%MOD;
}
}
a = a^1;
}
ll sum = 0;
for(int i=1;i<=100;i++)
{
sum = (sum+pow2[i]*tmp[a][i])%MOD;
}
save1[n][m] = sum;
}
}
long long ans[10][10]={2LL,4LL,8LL,16LL,32LL,64LL,128LL,256LL,512LL,1024LL,4LL,48LL,448LL,3840LL,31744LL,258048LL,2080768LL,16711680LL,133955584LL,72693241LL,8LL,448LL,15008LL,429568LL,11596928LL,306009088LL,2369992LL,530422352LL,523796386LL,215597769LL,16LL,3840LL,429568LL,38529024LL,207602155LL,200364260LL,160231949LL,554488410LL,190587140LL,810639015LL,32LL,31744LL,11596928LL,207602155LL,519052755LL,105908051LL,72277468LL,23284327LL,286851052LL,865424583LL,64LL,258048LL,306009088LL,200364260LL,105908051LL,126514477LL,312460128LL,711245882LL,987939142LL,374773317LL,128LL,2080768LL,2369992LL,160231949LL,72277468LL,312460128LL,25696077LL,433482528LL,357533852LL,103280608LL,256LL,16711680LL,530422352LL,554488410LL,23284327LL,711245882LL,433482528LL,162005329LL,771914613LL,811634190LL,512LL,133955584LL,523796386LL,190587140LL,286851052LL,987939142LL,357533852LL,771914613LL,585919048LL,573168128LL,1024LL,72693241LL,215597769LL,810639015LL,865424583LL,374773317LL,103280608LL,811634190LL,573168128LL,935300639LL};
int main(int argc, const char * argv[]) {
for(int i=0;i<(1<<10);i++)
{
int tmp = 0;
for(int j=0;j<10;j++)
{
if( (i&(1<<j))!=0 )
tmp++;
}
save[i] = tmp;
}
for(int i=0;i<=100;i++)
{
int tmp =1 ;
for(int j=0;j<i;j++)
{
tmp *= 2;
tmp %= MOD;
}
pow2[i] = tmp;
}
//预处理3
get_C();
get_fff();
memset(mark,-1,sizeof(mark));
for(int n=1;n<=10;n++)
{
for(int m=1;m<=10;m++)
{
//cout<<dfs((1<<n)-1-1,(1<<m)-1,0,1)<<"LL,";
}
}
int n,m;
while(cin>>n>>m)
{
cout<<ans[n-1][m-1]<<endl;
}
return 0;
}
![]()
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define MAX_N 110
/*------------------常量区-------------------*/
const double INF = 1e10; // 无穷大
const double EPS = 1e-5; // 计算精度
const double PI = acos(-1.0);// PI
const int PINXING = 0; // 平行
const int XIANGJIAO = 1; // 相交
const int XIANGLI = 0; // 相离
const int GONGXIAN = 2; // 共线
const int CHONGDIE = -1; // 重叠
const int INSIDE = 1; // 点在图形内部
const int OUTSIDE = 0; // 点在图形外部
const int BORDER = 2; // 点在图形边界
/*-----------------类型定义区----------------*/
struct Point { // 二维点或矢量
double x, y;
//double angle, dis;
Point() {}
Point(double x0, double y0): x(x0), y(y0) {}
void read()
{
scanf("%lf%lf",&x,&y);
}
};
struct Line { // 二维的直线或线段
Point p1, p2;
Line() {}
Line(Point p10, Point p20): p1(p10), p2(p20) {}
void read()
{
scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
}
};
struct Rect { // 用长宽表示矩形的方法 w, h分别表示宽度和高度
double w, h;
Rect() {}
Rect(double _w,double _h) : w(_w),h(_h) {}
};
struct Rect_2 { // 表示矩形，左下角坐标是(xl, yl)，右上角坐标是(xh, yh)
double xl, yl, xh, yh;
Rect_2() {}
Rect_2(double _xl,double _yl,double _xh,double _yh) : xl(_xl),yl(_yl),xh(_xh),yh(_yh) {}
};
struct Circle { //圆
Point c;
double r;
Circle() {}
Circle(Point _c,double _r) :c(_c),r(_r) {}
};
typedef vector<Point> Polygon; // 二维多边形
typedef vector<Point> Points; // 二维点集
/*-------------------基本函数区---------------------*/
inline double max(double x,double y)
{
return x > y ? x : y;
}
inline double min(double x, double y)
{
return x > y ? y : x;
}
inline bool ZERO(double x) // x == 0
{
return (fabs(x) < EPS);
}
inline bool ZERO(Point p) // p == 0
{
return (ZERO(p.x) && ZERO(p.y));
}
inline bool EQ(double x, double y) // eqaul, x == y
{
return (fabs(x - y) < EPS);
}
inline bool NEQ(double x, double y) // not equal, x != y
{
return (fabs(x - y) >= EPS);
}
inline bool LT(double x, double y) // less than, x < y
{
return ( NEQ(x, y) && (x < y) );
}
inline bool GT(double x, double y) // greater than, x > y
{
return ( NEQ(x, y) && (x > y) );
}
inline bool LEQ(double x, double y) // less equal, x <= y
{
return ( EQ(x, y) || (x < y) );
}
inline bool GEQ(double x, double y) // greater equal, x >= y
{
return ( EQ(x, y) || (x > y) );
}
// 输出浮点数前，防止输出-0.00调用该函数进行修正！
inline double FIX(double x)
{
return (fabs(x) < EPS) ? 0 : x;
}
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
//-------------------3D 区域----------------------------//
struct Point3D { //三维点或矢量
double x, y, z;
Point3D() {}
Point3D(double x0, double y0, double z0): x(x0), y(y0), z(z0) {}
void read()
{
scanf("%lf%lf%lf",&x,&y,&z);
}
};
struct Line3D { // 三维的直线或线段
Point3D p1, p2;
Line3D() {}
Line3D(Point3D p10, Point3D p20): p1(p10), p2(p20) {}
void read()
{
scanf("%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p1.z,&p2.x,&p2.y,&p2.z);
}
};
struct Area3D{
Point3D p1,p2,p3;
Area3D(){}
Area3D(Point3D p10, Point3D p20,Point3D p30): p1(p10), p2(p20), p3(p30){}
void read()
{
p1.read(); p2.read(); p3.read();
//scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p1.z,&p2.x,&p2.y,&p2.z,&p3.x,&p3.y,&p3.z);
}
};
inline bool ZERO(Point3D p) // p == 0
{
return (ZERO(p.x) && ZERO(p.y) && ZERO(p.z));
}
//////////////////////////////////////////////////////////////////////////////////////
//三维矢量运算
bool operator==(Point3D p1, Point3D p2)
{
return ( EQ(p1.x, p2.x) && EQ(p1.y, p2.y) && EQ(p1.z, p2.z) );
}
bool operator<(Point3D p1, Point3D p2)
{
if (NEQ(p1.x, p2.x)) {
return (p1.x < p2.x);
} else if (NEQ(p1.y, p2.y)) {
return (p1.y < p2.y);
} else {
return (p1.z < p2.z);
}
}
Point3D operator+(Point3D p1, Point3D p2)
{
return Point3D(p1.x + p2.x, p1.y + p2.y, p1.z + p2.z);
}
Point3D operator-(Point3D p1, Point3D p2)
{
return Point3D(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
}
Point3D operator * (const Point3D& A, double p) { return Point3D(A.x*p, A.y*p, A.z*p); }
Point3D operator / (const Point3D& A, double p) { return Point3D(A.x/p, A.y/p, A.z/p); }
Point3D operator*(Point3D p1, Point3D p2) // 计算叉乘 p1 x p2
{
return Point3D(p1.y * p2.z - p1.z * p2.y,
p1.z * p2.x - p1.x * p2.z,
p1.x * p2.y - p1.y * p2.x );
}
double operator&(Point3D p1, Point3D p2) { // 计算点积 p1·p2
return (p1.x * p2.x + p1.y * p2.y + p1.z * p2.z);
}
double Norm(Point3D p) // 计算矢量p的模
{
return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}
//取平面法向量
Point3D GetV(Area3D s){
return (s.p1-s.p2)*(s.p2-s.p3);
}
//判三点共线
int PointOnLine(Point3D p1,Point3D p2,Point3D p3){
return ZERO( (p1-p2)*(p2-p3) );
}
//判四点共面
int PointOnArea(Point3D a,Point3D b,Point3D c,Point3D d){
return ZERO( GetV(Area3D(a, b, c))&(d-a) );
}
//求三维空间中两点间的距离
double Dis(Point3D p1, Point3D p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
// 求三维空间中点到直线的距离
double Dis(Point3D p, Line3D L)
{
if(L.p1==L.p2) return Dis(p, L.p1);
return Norm((p - L.p1) * (L.p2 - L.p1)) / Norm(L.p2 - L.p1);
}
bool OnLine(Point3D p, Line3D L) // 判断三维空间中点p是否在直线L上
{
if(L.p1==L.p2 && p==L.p1) return true;//共点时，返回true
return ZERO( (p - L.p1) * (L.p2 - L.p1) );
}
bool OnLineSeg(Point3D p, Line3D L) // 判断三维空间中点p是否在线段l上
{
return ( ZERO((L.p1 - p) * (L.p2 - p)) &&
EQ( Norm(p - L.p1) + Norm(p - L.p2), Norm(L.p2 - L.p1)) );
}
// 点p到平面Ap-Al的距离。
double Dis(Point3D p, Point3D Ap, Point3D Al) {
return fabs((p-Ap)&Al)/Norm(Al); // 如果不取绝对值，得到的是有向距离
}
// 点p在平面Ap-Al上的投影。
Point3D PointToArea(Point3D p,Point3D Ap, Point3D Al) {
Al=Al/(Norm(Al));//把Al变成法向量。
return p-Al*((p-Ap)&Al);
}
//得到点p到直线L的距离，并返回p到直直线L的最近点rep
double PointToLine(Point3D p,Line3D L,Point3D& rep)
{
if(L.p1==L.p2)
{
rep=L.p1;
return Dis(p,L.p1);
}
Point3D a,b;
a = L.p2-L.p1;
b = p-L.p1;
double dis12 = Dis(L.p1,L.p2);
double dis = ( Norm(a*b) )/dis12;
double k = (a&b)/(Norm(a)*dis12) ;
rep = L.p1+(L.p2-L.p1)*k;
return dis;
}
//求两条直线之间的关系（三维）
//输入：两条不为点的直线
//输出：相交返回XIANGJIAO和交点p,平行返回PINGXING,共线返回GONGXIAN
int LineAndLine(Line3D L1,Line3D L2,Point3D &p)
{
Point3D px,py;
px = L1.p1 - L1.p2;
py = L2.p1 - L2.p2;
if( ZERO(px*py) )//平行或者共线
{
if( ZERO( (L2.p1-L1.p1)*py ) ) //共线
{
return GONGXIAN;
}
return PINXING;
}
//判断是否共面
Point3D tp=(L1.p1-L2.p1)*py;
if( !ZERO(tp&px) ) return XIANGLI;//XIANGLI与平行相同
p = L1.p1;
Point3D tp1=(L2.p1-L1.p1)*(L2.p1-L2.p2);
Point3D tp2=(L1.p2-L1.p1)*(L2.p1-L2.p2);
double _t = Norm(tp1)/Norm(tp2);
//tp1和tp2肯定是共线的，如果反向则_t 为负
if( LT( (tp1&tp2),0 ) ) _t*=-1;
p.x += (L1.p2.x-L1.p1.x)*_t;
p.y += (L1.p2.y-L1.p1.y)*_t;
p.z += (L1.p2.z-L1.p1.z)*_t;
return XIANGJIAO;
}
//空间两直线最近点对。直线不能平行，直线不能为点.
//ans1为直线a1,b1上的最近点
Point3D ans1,ans2;
double SegSegDistance(Point3D a1, Point3D b1, Point3D a2, Point3D b2)
{
Point3D v1 = (a1-b1), v2 = (a2-b2);
Point3D N = v1*v2;
Point3D ab = (a1-a2);
double ans = (N&ab) / Norm(N);
Point3D p1 = a1, p2 = a2;
Point3D d1 = b1-a1, d2 = b2-a2;
double t1, t2;
t1 = ((p2-p1)*d2 )&(d1*d2);
t2 = ((p2-p1)*d1 )&(d1*d2);
double dd = Norm( (d1*d2) );
t1 /= dd*dd;
t2 /= dd*dd;
ans1=a1+(b1-a1)*t1;
ans2=a2+(b2-a2)*t2;
return fabs(ans);
}
//直线与平面交
int LineAndArea(Line3D l1,Point3D Ap,Point3D Al,Point3D &p)
{
//输入直线，和平面的点法式
//第一步，判断直线与平面是否平行。
if( ZERO((l1.p2-l1.p1)&Al) ) return 0;//直线与平面平行。
double _t =( (Ap-l1.p1)&Al ) / ((l1.p1-l1.p2)&Al);
p = l1.p1+(l1.p1-l1.p2)*_t;
return 1;
}
void dfs(int x,double &len)
{
len++;
dfs(x-1,len);
dfs(x-2,len);
}
//空间两直线最近点对
//注意：直线不能平行
double LineAndLine(Line3D l1,Line3D l2,Point3D &p1,Point3D &p2)
{
//先求出法向量
Point3D v1,v2;
v1 = l1.p2-l1.p1;
v2 = l2.p2-l2.p1;
Point3D vt=v1*v2;
//然后先把l2投影到 l1所在的平面上
double len = ((l2.p1-l1.p1)&vt)/Norm(vt);
double normvt = -len/Norm(vt);
vt.x = vt.x*normvt;
vt.y = vt.y*normvt;
vt.z = vt.z*normvt;
Line3D tl2;
tl2.p1 = l2.p1+vt;
tl2.p2 = l2.p2+vt;
int sign=LineAndLine(l1, tl2, p1);
/*
//测试用
if(sign!=XIANGJIAO)
{
int x=0;
printf("%lf
",len/x);
dfs(100000000,len);
}
*/
return fabs(len);
}
//已知空间四面体6条边，求体积
double P( double a,double b,double c,double d,double e ){ return a*(b*c-d*e); }
double Get4V(int OA,int OB,int OC,int AB,int CA,int BC)
{
OA*=OA;OB*=OB;OC*=OC;AB*=AB;CA*=CA;BC*=BC;
double ans=0;
ans+=P( OA,OB,OC,(OB+OC-BC)/2.0,(OB+OC-BC)/2.0 );
ans-=P( (OA+OB-AB)/2.0,(OA+OB-AB)/2.0,OC,(OA+OC-CA)/2.0,(OB+OC-BC)/2.0 );
ans+=P( (OA+OC-CA)/2.0,(OA+OB-AB)/2.0,(OB+OC-BC)/2.0,OB,(OA+OC-CA)/2.0);
return sqrt(ans/36);
}
//求两面相交,平行或共面返回PINGXING,否则返回XIANGJIAO和直线rel
int AreaAndArea(Area3D a1,Area3D a2,Line3D &rel)
{
Point3D va1 = GetV(a1),va2 = GetV(a2);
Point3D lv = va1*va2;//相交直线的方向向量
if( ZERO(lv) )//平行
{
return PINXING;
}
//然后得到某一个交点
Point3D p1;
if(LineAndArea(Line3D(a1.p1,a1.p2), a2.p1, va2, p1) == 0)
if(LineAndArea(Line3D(a1.p1,a1.p3), a2.p1, va2, p1) == 0)
LineAndArea(Line3D(a1.p2,a1.p3), a2.p1, va2, p1);
rel.p1 = p1; rel.p2 = p1 + (lv*10);
return XIANGJIAO;
}
//////////////////////////////////////////////////////////////////////////////////////
/*---------------------代码区---------------------------*/
int equal3(Point3D p1,Point3D p2)
{
return p1.x==p2.x&&p1.y==p2.y&&p1.z==p2.z;
}
Area3D gettwoplanein(Area3D p1,Area3D p2,Point3D a,Point3D b)
{
Line3D l;
l.p1 = a; l.p2 = b;
Point3D pf1;//p1 的法向量
pf1 = GetV(p1);
//找一个不在交线上的点
Point3D p1d,p2d;
if( (!equal3(p1.p1,a)) && (!equal3(p1.p1, b)) ) p1d=p1.p1;
if( (!equal3(p1.p2,a)) && (!equal3(p1.p2, b)) ) p1d=p1.p2;
if( (!equal3(p1.p3,a)) && (!equal3(p1.p3, b)) ) p1d=p1.p3;
if( (!equal3(p2.p1,a)) && (!equal3(p2.p1, b)) ) p2d=p2.p1;
if( (!equal3(p2.p2,a)) && (!equal3(p2.p2, b)) ) p2d=p2.p2;
if( (!equal3(p2.p3,a)) && (!equal3(p2.p3, b)) ) p2d=p2.p3;
//然后对应到l上去
Point3D p1e,p2e;
PointToLine(p1d, l, p1e);
PointToLine(p2d, l, p2e);
p2d = p2d + (p1e-p2e);
//然后就是得到面上的一点
double l1 = Dis(p1d, p1e);
double l2 = Dis(p1e, p2d);
double l3 = Dis(p1d, p2d);
double shita = acos( (l1*l1+l2*l2-l3*l3)/(2*l1*l2) );
shita/=2;
double beta = acos( (l1*l1+l3*l3-l2*l2)/(2*l1*l3) );
beta = PI -shita -beta;
double x1 = l1*sin(shita)/sin(beta);
double x2 = l3-x1;
Point3D pp;
pp.x = p1d.x + (p2d.x-p1d.x)*x1/(x1+x2);
pp.y = p1d.y + (p2d.y-p1d.y)*x1/(x1+x2);
pp.z = p1d.z + (p2d.z-p1d.z)*x1/(x1+x2);
Area3D p3;
p3.p1 = a; p3.p2 = b; p3.p3 = pp;
return p3;
}
int main()
{
Point3D A,B,C,D;
while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&A.z,&B.x,&B.y,&B.z,&C.x,&C.y,&C.z,&D.x,&D.y,&D.z)!=EOF)
{
Area3D ABC,ABD,BCD,ACD;
ABC.p1 = A; ABC.p2 = B; ABC.p3 = C;
ABD.p1 = A; ABD.p2 = B; ABD.p3 = D;
BCD.p1 = B; BCD.p2 = C; BCD.p3 = D;
ACD.p1 = A; ACD.p2 = C; ACD.p3 = D;
//step one, 判断是存在四面体
if( PointOnArea(A,B,C,D) )
{
printf("O O O O
");
continue;
}
// 先得到三个角平分面
Area3D p1,p2,p3;
p1 = gettwoplanein(ABD, BCD, B, D);//讲道理，现在已经求出
p2 = gettwoplanein(ABC, BCD, B, C);
p3 = gettwoplanein(ABC, ACD, A, C);
//然后求三个面的交点
Line3D ll;
AreaAndArea(p1, p2, ll);
Point3D ans;
LineAndArea(ll, p3.p1, GetV(p3), ans);
double dis = Dis(ans, ABC.p1,GetV(ABC));
printf("%.4lf %.4lf %.4lf %.4lf
",ans.x,ans.y,ans.z,dis);
}
return 0;
}
