Submission #3040966

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
double pi=3.14159265359; //円周率
double EPS = 1e-10; //誤差

class point
{
	public:
	double x,y;
	int index;

	point()
	{x=0;y=0;index=0;}
	//コンストラクタ
	point(double a,double b)
	{
		x=a;y=b;index=0;
	}
	point(double a,double b,int i)
	{
		x=a;y=b;index=i;
	}
	//足し算
	point operator + (point p)
	{
		return point(x+p.x,y+p.y);
	}
	//引き算
	point operator - (point p)
	{
		return point(x-p.x,y-p.y);
	}
	//d倍
	point operator * (double d)
	{
		return point(x*d,y*d);
	}
	//x座標昇順でソートする
	bool operator < (const point &p)
	const {
		if(std::abs(x-p.x)>EPS)
			return x<p.x;
		else
			return y<p.y;
	}
	//内積
	//直交判定...abs(dot())<EPS
	double dot(point p)
	{
		return x*p.x+y*p.y;
	}
	//外積
	//平行判定...abs(cross())<EPS
	double cross(point p)
	{
		return x*p.y-y*p.x;
	}
	//絶対値を求める
	double abs()
	{
		return sqrt(x*x+y*y);
	}
	//単位ベクトルを求める
	point ev()
	{
		return point(x/abs(),y/abs());
	}
	//単位法線ベクトル（の1つ）を求める
	//もうひとつは-1倍することで求まる
	point nev()
	{
		return point(-y/abs(),x/abs());
	}
	//2点間の距離を求める
	//distがEPS未満なら2点は同じ位置にあるとみなす
	double pdist(point p)
	{
		point v=point(p.x-x,p.y-y);
		return v.abs();
	}
	//この点と直線p1-p2の距離を求める
	double ldist(point p1,point p2)
	{
		return std::abs((p2.y-p1.y)*x-(p2.x-p1.x)*y+p2.x*p1.y+p2.y*p1.x)/(p2-p1).abs();
	}

};

//線分p1-p2上に点qがあるか判定
bool on_seg(point p1,point p2,point q)
{
	return abs((p1-q).cross(p2-q))<EPS && (p1-q).dot(p2-q)<=EPS;
}
//直線p1-p2と直線q1-q2の交点
//線分の交差判定はこれの戻り値が線分上にあるかどうかで判定する...on_seg(p1,p2,intersection(p1,p2,q1,q2))
point intersection(point p1,point p2,point q1,point q2)
{
	return p1 + (p2-p1) * ((q2-q1).cross(q1-p1) / (q2-q1).cross(p2-p1));
}
//n頂点からなる多角形の面積を求める(vectorで頂点は与えられる)
double area(vector<point> p)
{
	double ret=0;
	for(int i=0;i<p.size()-1;i++)
	{
		ret+=p[i].cross(p[i+1]);
	}
	ret+=p[p.size()-1].cross(p[0]);
	ret/=2;
	return ret;
}
/*
3点a,b,cをa->b->cと進むとき、
* a->bで時計方向に折れてb->c (clockwise)
* a->bで反時計方向に折れてb->c(counter clockwise)
* a->bで逆を向いてaを通り越してb->c(c--a--b on line)
* a->bでそのままb->c(a--b--c on line)
* a->bで逆を向いてb->c(a--c--b on line)

のいずれのパターンかを判定する
*/
int ccw(point a,point b,point c)
{
	b=b-a;c=c-a;
	if(b.cross(c)>EPS)
		return 1; //counter clockwise
	if(b.cross(c)<-EPS)
		return -1; //clockwise
	if(b.dot(c)<-EPS)
		return 2; //c--a--b on line
	if(b.x*b.x+b.y*b.y < c.x*c.x+c.y*c.y)
		return -2; //a--b--c on line
	return 0; //a--c--b on line
}
//凸包を求める
vector<point> convex_hull(vector<point> p)
{
	int n=p.size();
	int k=0;
	sort(p.begin(),p.end());
	vector<point> ch(2*n);
	//lower-hull 下側凸包
	for(int i=0;i<n;ch[k++]=p[i++])
	{
		while(k>=2 && ccw(ch[k-2],ch[k-1],p[i])<=0)
			k--;
	}
	//upper-hull 上側凸包
	for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--])
	{
		while(k>=t && ccw(ch[k-2],ch[k-1],p[i])<=0)
			k--;
	}
	ch.resize(k-1);
	return ch;
}
vector<point> con;//凸法を求める
vector<point> p;//残っている点
point t[300];
bool tf[300];//残っている木を記録する
vector<tuple<int,int,int>> ans;
int main()
{
	for(int i=0;i<300;i++)
	{
		double x,y;
		cin>>x>>y;
		t[i]=point(x,y,i+1);
		p.push_back(t[i]);
		tf[i]=true;
	}
	while(1)
	{
		con = convex_hull(p); //全体の凸包を求める
		if(con.size()<3)
			break;
		//凸包から3つずつ区画を取る
		for(int i=0;i+2<con.size();i+=3)
		{
			ans.push_back(make_tuple(con[i].index,con[i+1].index,con[i+2].index));
			tf[con[i].index-1]=false;
			tf[con[i].index-1]=false;
			tf[con[i].index-1]=false;
		}
		//次のデータを入れる
		p.clear();
		{
			if(tf[i])
				p.push_back(t[i]);
		}
	}

	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++)
	{
		cout<<get<0>(ans[i])<<" "<<get<1>(ans[i])<<" "<<get<2>(ans[i])<<endl;
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:190:10: error: ‘i’ was not declared in this scope
    if(tf[i])
          ^