OUPC2012 問題I Plane Division (AOJ2358)

問題

日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2358

制約条件

入力は全て整数
n≦20
-100≦A,B,C,D,E,F≦100
-100≦Ai,Bi,Ci≦100
Ai≠0またはBi≠0
曲線は二次曲線
同一の直線が存在しうる

方針

解説スライド(http://www.slideshare.net/oupc)がわかりやすい。


二次曲線と直線の交点、および直線と直線の交点を全て求め、
オイラーの定理から面の数を求める。


二次曲線と直線の交点の式、直線と直線の交点の式は頑張って数学して求める。
オイラーの定理は、連結な場合に成り立つので、
二次曲線が楕円で、なおかつ直線と共有点を持たない場合は答えが+1

ソースコード

typedef complex<double> P;
bool sameline(int a,int b,int c,int p,int q,int r){
	if(a*q!=b*p)return 0;
	if(a==0)return b*r==c*q;
	return a*r==c*p;
}
void push(vector<P> &v,const P &p){
	rep(i,v.size())if(abs(v[i]-p)<EPS)return;
	v.pb(p);
}
P crosspoint(const pair<pi,int> &a,const pair<pi,int> &b){
	int a1=a.F.F,b1=a.F.S,c1=a.S,a2=b.F.F,b2=b.F.S,c2=b.S;
	double x=(-b2*c1+b1*c2)*1.0/(a1*b2-a2*b1),y=(a2*c1-a1*c2)*1.0/(a1*b2-a2*b1);
	return P(x,y);
}

int n,a,b,c,d,e,f;
vector<pair<pi,int> > ls;
vector<P> cps[20],cp;
vector<P> pts;

vector<P> cpLC(const pair<pi,int> &l){
	int a1=a,b1=b,c1=c,d1=d,e1=e,f1=f,d2=l.F.F,e2=l.F.S,f2=l.S;
	if(e2==0){
		swap(a1,c1); swap(d1,e1); swap(d2,e2);
	}
	vector<P> res;
	int p=a1*e2*e2-b1*e2*d2+c1*d2*d2;
	int q=-b1*e2*f2+2*c1*d2*f2+d1*e2*e2-e1*e2*d2;
	int r=c1*f2*f2-e1*e2*f2+f1*e2*e2;
	if(p==0){
		double x=-r*1.0/q, y=(-f2-d2*x)/e2;
		res.pb(P(x,y));
	}
	else{
		ll D=(ll)q*q-4ll*p*r;
		if(D==0){
			double x=-q/2.0/p,y=(-f2-d2*x)/e2;
			res.pb(P(x,y));
		}
		else if(D>0){
			double x1=(-q+sqrt(q*1.0*q-4.0*p*r))/2/p,y1=(-f2-d2*x1)/e2;
			double x2=(-q-sqrt(q*1.0*q-4.0*p*r))/2/p,y2=(-f2-d2*x2)/e2;
			res.pb(P(x1,y1)); res.pb(P(x2,y2));
		}
	}
	if(d2==0)rep(i,res.size())swap(res[i].real(),res[i].imag());
	
	return res;
}

int main(){
	cin>>n>>a>>b>>c>>d>>e>>f;
	rep(i,n){
		int a,b,c;
		cin>>a>>b>>c;
		rep(j,ls.size())if(sameline(ls[j].F.F,ls[j].F.S,ls[j].S,a,b,c)){
			n--;
			goto NEXT;
		}
		ls.pb(mp(mp(a,b),c)); NEXT:;
	}
	rep(i,n)rep(j,i)if(ls[i].F.F*ls[j].F.S!=ls[i].F.S*ls[j].F.F){
		push(cps[i],crosspoint(ls[i],ls[j]));
		push(cps[j],crosspoint(ls[i],ls[j]));
	}
	rep(i,n){
		vector<P> tmp=cpLC(ls[i]);
		rep(j,tmp.size())push(cp,tmp[j]), push(cps[i],tmp[j]);
	}
	rep(i,n)rep(j,cps[i].size())push(pts,cps[i][j]);

	int ans=1-(int)pts.size();
	rep(i,n)ans+=cps[i].size()+1;
	if(b*b<4*a*c)ans+=max(1,(int)cp.size());
	else if(b*b==4*a*c)ans+=cp.size()+1;
	else ans+=cp.size()+2;
	
	cout<<ans<<endl;
	
	return 0;
}