Shen Huang's Blog

/* HDU 4617 多校第二场 三维几何题 G
 * 告诉你圆心以及圆上的两个点，圆柱是无限长的
 * 也就是说求圆柱中心的那个直线，枚举每个圆柱之间的距离
 * 如果小于
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define maxn 33
#define EPS 1e-8
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
struct point{	
	double x,y,z;
	point (){}
	point (double x,double y,double z):x(x),y(y),z(z){}
	point operator + (point a) {return point(x+a.x,y+a.y,z+a.z);}
	point operator - (point a) {return point(x-a.x,y-a.y,z-a.z);}
	point operator * (double a) {return point(x*a,y*a,z*a);}
	point operator / (double a) {return point(x/a,y/a,z/a);}
}pt[maxn][3],p[maxn],nor[maxn];
double r[maxn];
inline int dcmp(double x){ return (x>EPS)-(x<-EPS);}
inline double dot(point a,point b) {return a.x*b.x+a.y*b.y+a.z*b.z;}
inline point cross(point a,point b) {
	return point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);}
inline double veclen(point x) {return sqrt(dot(x,x));} 
inline double ptdis(point a,point b){return veclen(a-b);}
inline point vecunit(point x) {return x/veclen(x);}
bool lldis(point p1,point u,point p2,point v,double &s){//判断空间两条直线是否平行，平行则输出0，否则～
	double b=dot(u,u)*dot(v,v)-dot(u,v)*dot(u,v);
	if(dcmp(b)==0) return false;
	double a=dot(u,v)*dot(v,p1-p2)-dot(v,v)*dot(u,p1-p2);
	s=a/b;
	return true;
}
double p21(point p,point a,point b){//求平行直线距离
	point v1= b - a ,v2 =p -a;
	return veclen(cross(v1,v2))/veclen(v1);
}
int main(){
	int T,n;
	scanf("%d",&T);
	while(T--&&scanf("%d",&n))
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<3;j++){
				scanf("%lf%lf%lf",&pt[i][j].x,&pt[i][j].y,&pt[i][j].z);
				p[i]=pt[i][0];
				r[i]=veclen(pt[i][0]-pt[i][1]);
				nor[i]=cross(pt[i][1]-pt[i][0],pt[i][2]-pt[i][0]);
			}
		double ans=1e10;
		bool touch=0;
		for(int i=0;i<n&&!touch;i++)
			for(int j=i+1;j<n&&!touch;j++)
			{
				double s,t,dis;
				if(lldis(p[i],nor[i],p[j],nor[j],s)){
					lldis(p[j],nor[j],p[i],nor[i],t);
					point a=p[i]+nor[i]*s;
					point b=p[j]+nor[j]*t;
					dis=ptdis(a,b);
				}else dis=p21(p[i],p[j],p[j]+nor[j]);
				if(dis<=r[i]+r[j]) touch=1;
				ans=min(ans,dis-r[i]-r[j]);

			}
		if(touch) cout<<"Lucky"<<endl;
		else printf("%.2fn",ans);
	}
	return 0;
}

/* POJ 2362 简单DFS 加 简单减枝
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
using namespace std;
#define maxn 100
int st[maxn];
int n,side;
bool vis[maxn];
bool cmp(int a,int b)
{
	return a>b;
}
bool dfs(int bian,int len,int id)//边数，目前长度，现在的线段编号
{
	if(bian==3) return 1;
	vis[id]=1;
	for(int i=id;i<n;i++)
		if(!vis[i]){
			if(len+st[i]>side) continue;
			vis[i]=1;
			if(len+st[i]==side&&dfs(bian+1,0,0))
					return 1;
			if(len+st[i]<side&&dfs(bian,len+st[i],i))
				return 1;
			vis[i]=0;
	}
	return 0;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(vis,0,sizeof(vis));
		scanf("%d",&n);
		int total=0;
		for(int i=0;i<n;i++)
		{	
			scanf("%d",&st[i]);
			total+=st[i];
		}
		if(total%4!=0){
			printf("non");
			continue;
		}
		side=total/4;
		sort(st,st+n,cmp);
		if(st[0]>side){
			printf("non");
			continue;
		}
		if(dfs(0,0,0)){
			printf("yesn");
		}
		else printf("non");
	}
	return 0;
}