幾何コンテスト2013

Submission #3058342

Source codeソースコード

#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);
		p.push_back(t[i]);
		tf[i]=true;
	}
	for(int yy=0;yy<100;yy++)
	{
		con = convex_hull(p); //全体の凸包を求める
		vector<point> tri; //三角形の頂点
		if(con.size()<3)
			break;
		//凸包から2つ頂点を選ぶ
		tri.push_back(con[0]);
		tf[con[0].index]=false;
		tri.push_back(con[1]);
		tf[con[1].index]=false;
		//原点をtri[0]とする
		double m=99999;
		int mindex=0;
		for(int i=0;i<300;i++)
		{
			//まだ使われていない頂点なら偏角を求める
			if(tf[i])
			{
				double nai = (tri[1]-tri[0]).dot(t[i]-tri[0]);
				nai /= (tri[1]-tri[0]).abs();
				nai /= (t[i]-tri[0]).abs();
				nai=abs(nai-1.0f);
				if(nai<m)
				{
					mindex=i;
					m=nai;
				}
			}
		}
		tri.push_back(t[mindex]);
		tf[t[mindex].index]=false;
		ans.push_back(make_tuple(tri[0].index,tri[1].index,tri[2].index));
		//次のデータを入れる
		p.clear();
		for(int i=0;i<300;i++)
		{
			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])+1<<" "<<get<1>(ans[i])+1<<" "<<get<2>(ans[i])+1<<endl;
	}
	return 0;
}

Submission

Task問題 A - 役人
User nameユーザ名 Badlylucky
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 4923 Byte
File nameファイル名
Exec time実行時間 3 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Subtask00 1 / 1 11_rand00.txt
Subtask01 1 / 1 11_rand01.txt
Subtask02 1 / 1 11_rand02.txt
Subtask03 1 / 1 11_rand03.txt
Subtask04 1 / 1 11_rand04.txt
Subtask05 1 / 1 11_rand05.txt
Subtask06 1 / 1 11_rand06.txt
Subtask07 1 / 1 11_rand07.txt
Subtask08 1 / 1 11_rand08.txt
Subtask09 1 / 1 11_rand09.txt
Subtask10 1 / 1 11_rand10.txt
Subtask11 1 / 1 11_rand11.txt
Subtask12 1 / 1 11_rand12.txt
Subtask13 1 / 1 11_rand13.txt
Subtask14 1 / 1 11_rand14.txt
Subtask15 1 / 1 11_rand15.txt
Subtask16 1 / 1 11_rand16.txt
Subtask17 1 / 1 11_rand17.txt
Subtask18 1 / 1 11_rand18.txt
Subtask19 1 / 1 11_rand19.txt
Subtask20 1 / 1 11_rand20.txt
Subtask21 1 / 1 11_rand21.txt
Subtask22 1 / 1 11_rand22.txt
Subtask23 1 / 1 11_rand23.txt
Subtask24 1 / 1 11_rand24.txt
Subtask25 1 / 1 11_rand25.txt
Subtask26 1 / 1 11_rand26.txt
Subtask27 1 / 1 11_rand27.txt
Subtask28 1 / 1 11_rand28.txt
Subtask29 1 / 1 11_rand29.txt
Subtask30 1 / 1 11_rand30.txt
Subtask31 1 / 1 11_rand31.txt
Subtask32 1 / 1 11_rand32.txt
Subtask33 1 / 1 11_rand33.txt
Subtask34 1 / 1 11_rand34.txt
Subtask35 1 / 1 11_rand35.txt
Subtask36 1 / 1 11_rand36.txt
Subtask37 1 / 1 11_rand37.txt
Subtask38 1 / 1 11_rand38.txt
Subtask39 1 / 1 11_rand39.txt
Subtask40 1 / 1 11_rand40.txt
Subtask41 1 / 1 11_rand41.txt
Subtask42 1 / 1 11_rand42.txt
Subtask43 1 / 1 11_rand43.txt
Subtask44 1 / 1 11_rand44.txt
Subtask45 1 / 1 11_rand45.txt
Subtask46 1 / 1 11_rand46.txt
Subtask47 1 / 1 11_rand47.txt
Subtask48 1 / 1 11_rand48.txt
Subtask49 1 / 1 11_rand49.txt
Subtask50 1 / 1 11_rand50.txt
Subtask51 1 / 1 11_rand51.txt
Subtask52 1 / 1 11_rand52.txt
Subtask53 1 / 1 11_rand53.txt
Subtask54 1 / 1 11_rand54.txt
Subtask55 1 / 1 11_rand55.txt
Subtask56 1 / 1 11_rand56.txt
Subtask57 1 / 1 11_rand57.txt
Subtask58 1 / 1 11_rand58.txt
Subtask59 1 / 1 11_rand59.txt
Subtask60 1 / 1 11_rand60.txt
Subtask61 1 / 1 11_rand61.txt
Subtask62 1 / 1 11_rand62.txt
Subtask63 1 / 1 11_rand63.txt
Subtask64 1 / 1 11_rand64.txt
Subtask65 1 / 1 11_rand65.txt
Subtask66 1 / 1 11_rand66.txt
Subtask67 1 / 1 11_rand67.txt
Subtask68 1 / 1 11_rand68.txt
Subtask69 1 / 1 11_rand69.txt
Subtask70 1 / 1 11_rand70.txt
Subtask71 1 / 1 11_rand71.txt
Subtask72 1 / 1 11_rand72.txt
Subtask73 1 / 1 11_rand73.txt
Subtask74 1 / 1 11_rand74.txt
Subtask75 1 / 1 11_rand75.txt
Subtask76 1 / 1 11_rand76.txt
Subtask77 1 / 1 11_rand77.txt
Subtask78 1 / 1 11_rand78.txt
Subtask79 1 / 1 11_rand79.txt
Subtask80 1 / 1 11_rand80.txt
Subtask81 1 / 1 11_rand81.txt
Subtask82 1 / 1 11_rand82.txt
Subtask83 1 / 1 11_rand83.txt
Subtask84 1 / 1 11_rand84.txt
Subtask85 1 / 1 11_rand85.txt
Subtask86 1 / 1 11_rand86.txt
Subtask87 1 / 1 11_rand87.txt
Subtask88 1 / 1 11_rand88.txt
Subtask89 1 / 1 11_rand89.txt
Subtask90 1 / 1 11_rand90.txt
Subtask91 1 / 1 11_rand91.txt
Subtask92 1 / 1 11_rand92.txt
Subtask93 1 / 1 11_rand93.txt
Subtask94 1 / 1 11_rand94.txt
Subtask95 1 / 1 11_rand95.txt
Subtask96 1 / 1 11_rand96.txt
Subtask97 1 / 1 11_rand97.txt
Subtask98 1 / 1 11_rand98.txt
Subtask99 1 / 1 11_rand99.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
11_rand00.txt AC 3 ms 256 KB
11_rand01.txt AC 3 ms 256 KB
11_rand02.txt AC 3 ms 256 KB
11_rand03.txt AC 3 ms 256 KB
11_rand04.txt AC 3 ms 256 KB
11_rand05.txt AC 3 ms 256 KB
11_rand06.txt AC 3 ms 256 KB
11_rand07.txt AC 3 ms 256 KB
11_rand08.txt AC 3 ms 256 KB
11_rand09.txt AC 3 ms 256 KB
11_rand10.txt AC 3 ms 256 KB
11_rand11.txt AC 3 ms 256 KB
11_rand12.txt AC 3 ms 256 KB
11_rand13.txt AC 3 ms 256 KB
11_rand14.txt AC 3 ms 256 KB
11_rand15.txt AC 3 ms 256 KB
11_rand16.txt AC 3 ms 256 KB
11_rand17.txt AC 3 ms 256 KB
11_rand18.txt AC 3 ms 256 KB
11_rand19.txt AC 3 ms 256 KB
11_rand20.txt AC 3 ms 256 KB
11_rand21.txt AC 3 ms 256 KB
11_rand22.txt AC 3 ms 256 KB
11_rand23.txt AC 3 ms 256 KB
11_rand24.txt AC 3 ms 256 KB
11_rand25.txt AC 3 ms 256 KB
11_rand26.txt AC 3 ms 256 KB
11_rand27.txt AC 3 ms 256 KB
11_rand28.txt AC 3 ms 256 KB
11_rand29.txt AC 3 ms 256 KB
11_rand30.txt AC 3 ms 256 KB
11_rand31.txt AC 3 ms 256 KB
11_rand32.txt AC 3 ms 256 KB
11_rand33.txt AC 3 ms 256 KB
11_rand34.txt AC 3 ms 256 KB
11_rand35.txt AC 3 ms 256 KB
11_rand36.txt AC 3 ms 256 KB
11_rand37.txt AC 3 ms 256 KB
11_rand38.txt AC 3 ms 256 KB
11_rand39.txt AC 3 ms 256 KB
11_rand40.txt AC 3 ms 256 KB
11_rand41.txt AC 3 ms 256 KB
11_rand42.txt AC 3 ms 256 KB
11_rand43.txt AC 3 ms 256 KB
11_rand44.txt AC 3 ms 256 KB
11_rand45.txt AC 3 ms 256 KB
11_rand46.txt AC 3 ms 256 KB
11_rand47.txt AC 3 ms 256 KB
11_rand48.txt AC 3 ms 256 KB
11_rand49.txt AC 3 ms 256 KB
11_rand50.txt AC 3 ms 256 KB
11_rand51.txt AC 3 ms 256 KB
11_rand52.txt AC 3 ms 256 KB
11_rand53.txt AC 3 ms 256 KB
11_rand54.txt AC 3 ms 256 KB
11_rand55.txt AC 3 ms 256 KB
11_rand56.txt AC 3 ms 256 KB
11_rand57.txt AC 3 ms 256 KB
11_rand58.txt AC 3 ms 256 KB
11_rand59.txt AC 3 ms 256 KB
11_rand60.txt AC 3 ms 256 KB
11_rand61.txt AC 3 ms 256 KB
11_rand62.txt AC 3 ms 256 KB
11_rand63.txt AC 3 ms 256 KB
11_rand64.txt AC 3 ms 256 KB
11_rand65.txt AC 3 ms 256 KB
11_rand66.txt AC 3 ms 256 KB
11_rand67.txt AC 3 ms 256 KB
11_rand68.txt AC 3 ms 256 KB
11_rand69.txt AC 3 ms 256 KB
11_rand70.txt AC 3 ms 256 KB
11_rand71.txt AC 3 ms 256 KB
11_rand72.txt AC 3 ms 256 KB
11_rand73.txt AC 3 ms 256 KB
11_rand74.txt AC 3 ms 256 KB
11_rand75.txt AC 3 ms 256 KB
11_rand76.txt AC 3 ms 256 KB
11_rand77.txt AC 3 ms 256 KB
11_rand78.txt AC 3 ms 256 KB
11_rand79.txt AC 3 ms 256 KB
11_rand80.txt AC 3 ms 256 KB
11_rand81.txt AC 3 ms 256 KB
11_rand82.txt AC 3 ms 256 KB
11_rand83.txt AC 3 ms 256 KB
11_rand84.txt AC 3 ms 256 KB
11_rand85.txt AC 3 ms 256 KB
11_rand86.txt AC 3 ms 256 KB
11_rand87.txt AC 3 ms 256 KB
11_rand88.txt AC 3 ms 256 KB
11_rand89.txt AC 3 ms 256 KB
11_rand90.txt AC 3 ms 256 KB
11_rand91.txt AC 3 ms 256 KB
11_rand92.txt AC 3 ms 256 KB
11_rand93.txt AC 3 ms 256 KB
11_rand94.txt AC 3 ms 256 KB
11_rand95.txt AC 3 ms 256 KB
11_rand96.txt AC 3 ms 256 KB
11_rand97.txt AC 3 ms 256 KB
11_rand98.txt AC 3 ms 256 KB
11_rand99.txt AC 3 ms 256 KB