atcoderＤ三角形の分類 - sinapusu2002 @ ウィキ

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";
}