geometry


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

  • 点クラス 複素平面をイメージ
    class P{
    	static final double EPS=1e-10;
    	static int signum(double x){
    		return x<-EPS?-1:x>EPS?1:0;
    	}
    	static Comparator<P> comp = new Comparator<P>(){
    		public int compare(P p1, P p2) {
    			return signum(p1.x-p2.x)!=0?signum(p1.x-p2.x):signum(p1.y-p2.y);
    		}
    	};
    	public static final P O = new P(0,0);
    	final double x, y;
    	P(double _x,double _y){
    		x=_x;
    		y=_y;
    	}
    	//四則
    	P add(P a){
    		return new P(x+a.x,y+a.y);
    	}
    	P sub(P a){
    		return new P(x-a.x,y-a.y);
    	}
    	P mul(P a){
    		return new P(x*a.x-y*a.y,x*a.y+y*a.x);
    	}
    	P div(P a){
    		double d2=a.dist2(O);
    		return new P(dot(a,this)/d2,cross(a,this)/d2);
    	}
    	//共役
    	P conj(){
    		return new P(x,-y);
    	}
    	//内積 a・b=|a||b|cosθ=a.x*b.x+a.y*b.y
    	static double dot(P a,P b){
    		return  a.x*b.x+a.y*b.y;
    	}
    	//外積 a×b=|a||b|sinθ=a.x*b.y-a.y*b.x
    	static double cross(P a,P b){
    		return  a.x*b.y-a.y*b.x;
    	}
    	//二乗距離
    	double dist2(P p){
    		return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
    	}
    	//a,b間の距離
    	double dist(P p){
    		return sqrt(dist2(p));
    	}
    	public double norm(){
    		return dist(O);
    	}
    	// a→b→cと進むときの向き
    	static int ccw(P a,P b,P c){
    		b = b.sub(a); c = c.sub(a);
    		if(cross(b,c)>EPS) return 1;//counter clockwise
    		if(cross(b,c)<-EPS) return -1;//clockwise
    		if(dot(b,c)<-EPS) return 2;//c--a--b on line
    		if(b.norm()<c.norm()-EPS) return -2;//a--b--c on line
    		return 0;//a--c--b on line (or b==c)
    	}
    	//oからみたaの角度
    	static double arg(P a,P o){
    		P dir=a.sub(o);
    		double s=acos(dir.x/dir.norm());
    		return dir.y>0?s:2*PI-s;
    	}
    	//oを中心に回転
    	P rotate(P o,double arg){
    		return this.add(this.sub(o).mul(new P(cos(arg),sin(arg))));
    	}
    	//→OA,→OBの面積の2倍
    	static double S2(P a,P b,P o){
    		return cross(a.sub(o),b.sub(o));
    	}
    	static double S(P a,P b,P o){
    		return S2(a,b,o)/2;
    	}
    	//絶対値と偏角から座標を取得
    	static P polar(double abs,double arg){
    		return new P(abs*cos(arg),abs*sin(arg));
    	}
    	// ?
    	static P proj(P p,P o){
    		return o.mul(new P(dot(p,o)/o.norm(),0));
    	}
    	public boolean equals(Object obj) {
    		if(obj instanceof P){
    			P p=(P)obj;
    			return signum(x-p.x)==0 && signum(y-p.y)==0;
    		}
    		return false;
    	}
     
    	public String toString(){
    		return "("+x+","+y+")";
    	}
    }
  • 線クラス
    //(注)
    //dist,isIntersectは擬似的に二項関係の演算子として扱う
    //intersectionはPのコンストラクタとして扱う
    class L extends AL{
    	L(P _p1, P _p2) {super(_p1, _p2);}
     
    	//直線と点の距離
    	double dist(P p){
    		return abs(P.S(p2,p,p1))/p1.sub(p2).norm();
    	}
    	boolean isIntersect(P p){
    		return abs(P.S(p2,p,p1))<EPS;
    	}
    	boolean isIntersect(L l){
    		if(isPoint() && l.isPoint())return p1.equals(l.p1);
    		if(isPoint())return l.isIntersect(p1);
    		if(l.isPoint())return isIntersect(l.p1);
    		return !isParallel(l) || isIntersect(l.p1);
    	}
     
    	//垂線の足
    	static P FootOfLP(L l,P p){
    		return l.p1.add(P.proj(p.sub(l.p1),l.p2.sub(l.p1)));
    	}
     
    	//線対称な点
    	static P LineSymmetricLP(L l,P p){
    		return FootOfLP(l,p).mul(new P(2.0,0)).sub(p);
    	}
     
    	public boolean equals(Object obj) {
    		if(obj instanceof L){
    			L l=(L)obj;
    			return isParallel(l) && isIntersect(l.p1);
    		}
    		return false;
    	}
    }
    //線分
    class S extends AL{
    	S(P _p1, P _p2) {super(_p1, _p2);}
    	boolean isIntersect(P p){//|a-p|+|p-b|<=|a-b|
    		return p1.sub(p).norm()+p2.sub(p).norm()<=p1.sub(p2).norm()+EPS;
    	}
    	boolean isIntersect(L l){//l2の端点がl1の上か下か
    		return P.cross(l.p2.sub(l.p1),p1.sub(l.p1))*
    			P.cross(l.p2.sub(l.p1),p2.sub(l.p1))<EPS;
    	}
    	boolean isIntersect(S l){
    		return P.ccw(p1,p2,l.p1)*P.ccw(p1,p2,l.p2)<=0
    		&& P.ccw(l.p1,l.p2,p1)*P.ccw(l.p1,l.p2,p2)<=0;
    	}
    	//線分と点
    	double dist(P p){
    		if(P.dot(p2.sub(p1),p.sub(p1))<EPS)return p.sub(p1).norm();
    		if(P.dot(p1.sub(p2),p.sub(p2))<EPS)return p.sub(p2).norm();
    		return abs(P.S(p2,p,p1))/p1.sub(p2).norm();
    	}
    	//直線との距離
    	double dist(L l){
    		if(isIntersect(l))return 0;
    		return min(l.dist(p1),l.dist(p2));
    	}
    	//線分と線分
    	double dist(S l){
    		if(isIntersect(l))return 0;
    		return min(min(dist(l.p1),dist(l.p2)),min(l.dist(p1),l.dist(p2)));
    	}
    }
    abstract class AL{
    	//geo
    	static final double EPS=1e-10;
    	static int signum(double x){
    		return x<-EPS?-1:x>EPS?1:0;
    	}
    	public P p1,p2;
    	AL(P _p1,P _p2){
    		p1=_p1;
    		p2=_p2;
    	}
     
    	boolean isPoint(){
    		return p1.equals(p2);
    	}
     
    //	public double a(){
    //		P dir= p2.sub(p1);
    //		return dir.y/dir.x;
    //	}
    //	public double b(){
    //		return P.cross(p1,p2)/(p1.x-p2.x);
    //	}
     
    	//平行
    	boolean isParallel(AL l){
    		return abs(P.cross(p2.sub(p1),l.p2.sub(l.p1)))<EPS;
    	}
    	//直交
    	boolean isOrthogonal(AL l){
    		return abs(P.dot(p2.sub(p1),l.p2.sub(l.p1)))<EPS;
    	}
     
    	//交点 (交差判定なし)
    	static P intersection(AL l1,AL l2){
    		P dl1=l1.p2.sub(l1.p1),dl2=l2.p2.sub(l2.p1);
    		double a=P.cross(dl2,l2.p1.sub(l1.p1));
    		double b=P.cross(dl2,dl1);
    		if(abs(a)<EPS && abs(b) <EPS)return l1.p1;//same
    		return l1.p1.add(dl1.mul(new P(a/b,0.0)));
    	}
     
     
    	public boolean equals(Object obj) {
    		if(obj instanceof L){
    			L l=(L)obj;
    			return this.p1.equals(l.p1) && this.p2.equals(l.p2);
    		}
    		return false;
    	}
    	public String toString(){
    		return p1+"-"+p2;
    	}
    }