「atcoderＤ三角形の分類」の編集履歴（バックアップ）一覧に戻る

atcoderＤ三角形の分類 - (2016/10/08 (土) 17:10:07) のソース

2 次元平面上の N 個の点が与えられます。 i 番目の点の座標は (xi,yi) です。ただし、このうちのどの 3 点も同一直線上にありません。

N 点のうち 3 点を選ぶことによってこの 3 点を頂点とした三角形を作ることを考えます。三角形は全部で N*(N−1)*(N−2)⁄6 個できます。 これらの三角形のうち、鋭角三角形の個数、直角三角形の個数、鈍角三角形の個数を求めてください。

ただし、鋭角三角形とは、3 つの角が全て 90° より小さい三角形で、直角三角形とは、ある 1 つの角が 90° である三角形で、 鈍角三角形とは、ある 1 つの角が 90° より大きい三角形のことをいいます。

Ｎ＜＝2000


２点を適当に選び一点を原点Ｏ、一点をＡ0とする。
その２点からみて半時計回りに点を整列しＡ0～Ａｎ-２とする。
後は、Ａ0からみて鈍角になるＡｉＯＡ0～ＡｊＯＡ0の範囲を求める。
Ａ1OＡｉが鈍角になるＡｉの範囲はＡＩＯＡ0を少し回せばいいので尺取虫法で解けると分かる。
ＯＡｋＡiを少し回すとＯＡｋ+1Ａiが鈍角になる範囲はすぐにわかる。
一周くるりと回せばよい。

後はこれを全ての点をＯにして繰り返す。
Ｐｒｏｌｏｇ的発想。

自力解法で30/260位。
１位は圧倒的だな。
私は４流アマチュアプログラマとして最底辺を徘徊するだけです。


 #include<stdio.h>
 #include<math.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 #include<string.h>
  
 double calcCosA(double x1,double y1,double x2,double y2,double x3,double y3){
	double dx2=x2-x1;
	double dy2=y2-y1;
	double dx3=x3-x1;
	double dy3=y3-y1;
	return (dx2*dx3+dy2*dy3)/(hypot(dx2,dy2)*hypot(dx3,dy3));
 }
 double calcSinA(double x1,double y1,double x2,double y2,double x3,double y3){
	double dx2=x2-x1;
	double dy2=y2-y1;
	double dx3=x3-x1;
	double dy3=y3-y1;
	return (dx2*dy3-dy2*dx3)/(hypot(dx2,dy2)*hypot(dx3,dy3));
 }
  
 int naiseki(int x0,int y0,int x1,int y1,int x2,int y2){
	int dx1=x1-x0;
	int dy1=y1-y0;
	int dx2=x2-x0;
	int dy2=y2-y0;
	return dx1*dx2+dy1*dy2;
 }
 int gaiseki(int x0,int y0,int x1,int y1,int x2,int y2){
	int dx1=x1-x0;
	int dy1=y1-y0;
	int dx2=x2-x0;
	int dy2=y2-y0;
	return dx1*dy2-dx2*dy1;
 }
 struct E{
	int x,y;
	double cosA,sinA;
	bool operator<(const E& e)const{
		if((sinA>=0)&&(e.sinA>=0)){
			return cosA>e.cosA;
		}else if((sinA>=0)&&(e.sinA<0)){
			return true;
		}else if((sinA<0)&&(e.sinA>=0)){
			return false;
		}else{
			return cosA<e.cosA;
		}
	}
 };
  
 int main(){
	int n;
	int xs[2001],ys[2001];
	scanf("%d",&n);
	long long int ans0=0,ans1=0,ans2=0,n1=n;
	for(int i=0;i<n;i++){
		scanf("%d %d",&xs[i],&ys[i]);
	}
 
	int c=0;
	for(int i=0;i<n;i++){
		E e1;
		int k=(i+1)%n;
		std::vector<E> vec;
		for(int j=0;j<n;j++){
			if(j==i)continue;
			e1.x=xs[j];
			e1.y=ys[j];
			e1.cosA=calcCosA(xs[i],ys[i],xs[k],ys[k],xs[j],ys[j]);
			e1.sinA=calcSinA(xs[i],ys[i],xs[k],ys[k],xs[j],ys[j]);
			vec.push_back(e1);
		}
		std::sort(vec.begin(),vec.end());
		int x0=xs[i];
		int y0=ys[i];
		int p1=1;
		int p2=1;
		int pp1=(vec.size()-1);
		int pp2=pp1;
		for(int j=0;j<vec.size();j++)
		{
			//反時計回り
			int x1=vec[j].x;
			int y1=vec[j].y;
			//printf("(%d %d)",x1-x0,y1-y0);
 
			if(j==p1){
				p1=(p1+1)%vec.size();
			}
			bool bad=false;
			int type=0;
			while(1){
				int x2=vec[p1].x;
				int y2=vec[p1].y;
				int d=naiseki(x0,y0,x1,y1,x2,y2);
				int g=gaiseki(x0,y0,x1,y1,x2,y2);
				if((d==0)&&(g>0)){				
					ans1++;
					break;
				}
				if((d<=0)&&(g>0)){
					break;
				}
				if(g<0){
					bad=true;
					break;
				}
				p1=(p1+1)%vec.size();
				if(p1==j){
					bad=true;
					break;
				}
			}
			if(p1!=j){
				bool bad2=false;
				while(1){
					int x2=vec[p2].x;
					int y2=vec[p2].y;
					int g=gaiseki(x0,y0,x1,y1,x2,y2);
					if(g<0)break;
					p2=(p2+1)%vec.size();
					if(p2==j){
						break;
					}
				}	
				if(bad==false&&bad2==false){
					if(p1<p2){
						ans2+=p2-p1;
					}else if(p1>p2){
						ans2+=(vec.size()-p1+p2);
					}
					//printf("%d\n",ans2);
				}
			}
		}
	}
 
	std::cout<<n1*(n1-1)*(n1-2)/6-ans2<<" "<<ans1<<" "<<ans2-ans1<<"\n";
 }