幾何コンテスト2013

Submission #3058566

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;

	point()
	{x=0;y=0;}
	//コンストラクタ
	point(double a,double b)
	{
		x=a;y=b;
	}

	//足し算
	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> kagum;//マイナス側の家具
bool m[100];
vector<point> kagup;//プラス側の家具
bool p[100];
int main()
{
	int n;
	cin>>n;
	double ans=0;
	for(int i=0;i<n;i++)
	{
		double x,y;
		cin>>x>>y;
		if(x>0)
			kagup.push_back(point(x,y));
		else if(x<0)
			kagum.push_back(point(x,y));
	}
	sort(kagum.begin(),kagum.end());
	reverse(kagum.begin(),kagum.end());//プラス側の家具はx座標降順にソート
	sort(kagup.begin(),kagup.end());//マイナス側の家具はx座標昇順にソート
	fill(m,m+kagum.size(),true);
	fill(p,p+kagup.size(),true);
	//それぞれについてペアを調べる
	for(int i=0;i<kagup.size();i++)
	{
		double mdiff=kagup[i].x; //移動量の初期値はx座標
		point tai = point(-kagup[i].x,kagup[i].y); //y軸について対称な座標
		//taiに最も近いkagumの要素を求める
		int mindex=-1;
		for(int j=0;j<kagum.size();j++)
		{
			if(m[j])
			{
				double d=tai.pdist(kagum[j]);
				if(d<mdiff)
				{
					mdiff=d;
					mindex=j;
				}
			}
		}
		//ペアが求まっていればそれにする
		//移動量は対称な座標との距離に等しい
		p[i]=false;
		if(mindex!=-1)
		{
			m[mindex]=false;
			ans+=mdiff;
		}else{
			//ペアができてなければy軸上に移動させる
			ans+=mdiff;
		}
	}
	//マイナス側から使われなかった頂点を調べる
	for(int i=0;i<kagum.size();i++)
	{
		if(m[i])
		{
			//使われなかった頂点はx軸上に移動させる
			ans+=abs(kagum[i].x);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission

Task問題 B - 玉座の間
User nameユーザ名 Badlylucky
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 50
Source lengthソースコード長 5003 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 50 / 50 11_rand00.txt,11_rand01.txt,11_rand02.txt,11_rand03.txt,11_rand04.txt,11_rand05.txt,11_rand06.txt,11_rand07.txt,11_rand08.txt,11_rand09.txt,11_rand10.txt,11_rand11.txt,11_rand12.txt,11_rand13.txt,11_rand14.txt,11_rand15.txt,11_rand16.txt,11_rand17.txt,11_rand18.txt,11_rand19.txt,11_rand20.txt,11_rand21.txt,11_rand22.txt,11_rand23.txt,11_rand24.txt
Subtask2 0 / 50 11_rand00.txt,11_rand01.txt,11_rand02.txt,11_rand03.txt,11_rand04.txt,11_rand05.txt,11_rand06.txt,11_rand07.txt,11_rand08.txt,11_rand09.txt,11_rand10.txt,11_rand11.txt,11_rand12.txt,11_rand13.txt,11_rand14.txt,11_rand15.txt,11_rand16.txt,11_rand17.txt,11_rand18.txt,11_rand19.txt,11_rand20.txt,11_rand21.txt,11_rand22.txt,11_rand23.txt,11_rand24.txt,21_rand00.txt,21_rand01.txt,21_rand02.txt,21_rand03.txt,21_rand04.txt,21_rand05.txt,21_rand06.txt,21_rand07.txt,21_rand08.txt,21_rand09.txt,21_rand10.txt,21_rand11.txt,21_rand12.txt,21_rand13.txt,21_rand14.txt,21_rand15.txt,21_rand16.txt,21_rand17.txt,21_rand18.txt,21_rand19.txt,21_rand20.txt,21_rand21.txt,21_rand22.txt,21_rand23.txt,21_rand24.txt
Subtask3 0 / 50 11_rand00.txt,11_rand01.txt,11_rand02.txt,11_rand03.txt,11_rand04.txt,11_rand05.txt,11_rand06.txt,11_rand07.txt,11_rand08.txt,11_rand09.txt,11_rand10.txt,11_rand11.txt,11_rand12.txt,11_rand13.txt,11_rand14.txt,11_rand15.txt,11_rand16.txt,11_rand17.txt,11_rand18.txt,11_rand19.txt,11_rand20.txt,11_rand21.txt,11_rand22.txt,11_rand23.txt,11_rand24.txt,21_rand00.txt,21_rand01.txt,21_rand02.txt,21_rand03.txt,21_rand04.txt,21_rand05.txt,21_rand06.txt,21_rand07.txt,21_rand08.txt,21_rand09.txt,21_rand10.txt,21_rand11.txt,21_rand12.txt,21_rand13.txt,21_rand14.txt,21_rand15.txt,21_rand16.txt,21_rand17.txt,21_rand18.txt,21_rand19.txt,21_rand20.txt,21_rand21.txt,21_rand22.txt,21_rand23.txt,21_rand24.txt,31_rand00.txt,31_rand01.txt,31_rand02.txt,31_rand03.txt,31_rand04.txt,31_rand05.txt,31_rand06.txt,31_rand07.txt,31_rand08.txt,31_rand09.txt,31_rand10.txt,31_rand11.txt,31_rand12.txt,31_rand13.txt,31_rand14.txt,31_rand15.txt,31_rand16.txt,31_rand17.txt,31_rand18.txt,31_rand19.txt,31_rand20.txt,31_rand21.txt,31_rand22.txt,31_rand23.txt,31_rand24.txt
Subtask4 0 / 50 11_rand00.txt,11_rand01.txt,11_rand02.txt,11_rand03.txt,11_rand04.txt,11_rand05.txt,11_rand06.txt,11_rand07.txt,11_rand08.txt,11_rand09.txt,11_rand10.txt,11_rand11.txt,11_rand12.txt,11_rand13.txt,11_rand14.txt,11_rand15.txt,11_rand16.txt,11_rand17.txt,11_rand18.txt,11_rand19.txt,11_rand20.txt,11_rand21.txt,11_rand22.txt,11_rand23.txt,11_rand24.txt,21_rand00.txt,21_rand01.txt,21_rand02.txt,21_rand03.txt,21_rand04.txt,21_rand05.txt,21_rand06.txt,21_rand07.txt,21_rand08.txt,21_rand09.txt,21_rand10.txt,21_rand11.txt,21_rand12.txt,21_rand13.txt,21_rand14.txt,21_rand15.txt,21_rand16.txt,21_rand17.txt,21_rand18.txt,21_rand19.txt,21_rand20.txt,21_rand21.txt,21_rand22.txt,21_rand23.txt,21_rand24.txt,31_rand00.txt,31_rand01.txt,31_rand02.txt,31_rand03.txt,31_rand04.txt,31_rand05.txt,31_rand06.txt,31_rand07.txt,31_rand08.txt,31_rand09.txt,31_rand10.txt,31_rand11.txt,31_rand12.txt,31_rand13.txt,31_rand14.txt,31_rand15.txt,31_rand16.txt,31_rand17.txt,31_rand18.txt,31_rand19.txt,31_rand20.txt,31_rand21.txt,31_rand22.txt,31_rand23.txt,31_rand24.txt,41_rand00.txt,41_rand01.txt,41_rand02.txt,41_rand03.txt,41_rand04.txt,41_rand05.txt,41_rand06.txt,41_rand07.txt,41_rand08.txt,41_rand09.txt,41_rand10.txt,41_rand11.txt,41_rand12.txt,41_rand13.txt,41_rand14.txt,41_rand15.txt,41_rand16.txt,41_rand17.txt,41_rand18.txt,41_rand19.txt,41_rand20.txt,41_rand21.txt,41_rand22.txt,41_rand23.txt,41_rand24.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
11_rand00.txt AC 1 ms 256 KB
11_rand01.txt AC 1 ms 256 KB
11_rand02.txt AC 1 ms 256 KB
11_rand03.txt AC 1 ms 256 KB
11_rand04.txt AC 1 ms 256 KB
11_rand05.txt AC 1 ms 256 KB
11_rand06.txt AC 1 ms 256 KB
11_rand07.txt AC 1 ms 256 KB
11_rand08.txt AC 1 ms 256 KB
11_rand09.txt AC 1 ms 256 KB
11_rand10.txt AC 1 ms 256 KB
11_rand11.txt AC 1 ms 256 KB
11_rand12.txt AC 1 ms 256 KB
11_rand13.txt AC 1 ms 256 KB
11_rand14.txt AC 1 ms 256 KB
11_rand15.txt AC 1 ms 256 KB
11_rand16.txt AC 1 ms 256 KB
11_rand17.txt AC 1 ms 256 KB
11_rand18.txt AC 1 ms 256 KB
11_rand19.txt AC 1 ms 256 KB
11_rand20.txt AC 1 ms 256 KB
11_rand21.txt AC 1 ms 256 KB
11_rand22.txt AC 1 ms 256 KB
11_rand23.txt AC 1 ms 256 KB
11_rand24.txt AC 1 ms 256 KB
21_rand00.txt AC 1 ms 256 KB
21_rand01.txt AC 1 ms 256 KB
21_rand02.txt WA
21_rand03.txt AC 1 ms 256 KB
21_rand04.txt WA
21_rand05.txt WA
21_rand06.txt AC 1 ms 256 KB
21_rand07.txt AC 1 ms 256 KB
21_rand08.txt WA
21_rand09.txt AC 1 ms 256 KB
21_rand10.txt WA
21_rand11.txt WA
21_rand12.txt WA
21_rand13.txt WA
21_rand14.txt WA
21_rand15.txt WA
21_rand16.txt WA
21_rand17.txt WA
21_rand18.txt WA
21_rand19.txt WA
21_rand20.txt WA
21_rand21.txt AC 1 ms 256 KB
21_rand22.txt AC 1 ms 256 KB
21_rand23.txt AC 1 ms 256 KB
21_rand24.txt WA
31_rand00.txt AC 1 ms 256 KB
31_rand01.txt AC 1 ms 256 KB
31_rand02.txt WA
31_rand03.txt WA
31_rand04.txt WA
31_rand05.txt WA
31_rand06.txt WA
31_rand07.txt WA
31_rand08.txt WA
31_rand09.txt WA
31_rand10.txt WA
31_rand11.txt WA
31_rand12.txt WA
31_rand13.txt WA
31_rand14.txt WA
31_rand15.txt WA
31_rand16.txt AC 1 ms 256 KB
31_rand17.txt WA
31_rand18.txt WA
31_rand19.txt WA
31_rand20.txt WA
31_rand21.txt WA
31_rand22.txt WA
31_rand23.txt WA
31_rand24.txt WA
41_rand00.txt WA
41_rand01.txt AC 1 ms 256 KB
41_rand02.txt WA
41_rand03.txt WA
41_rand04.txt WA
41_rand05.txt WA
41_rand06.txt WA
41_rand07.txt WA
41_rand08.txt WA
41_rand09.txt WA
41_rand10.txt AC 1 ms 256 KB
41_rand11.txt WA
41_rand12.txt WA
41_rand13.txt WA
41_rand14.txt WA
41_rand15.txt WA
41_rand16.txt WA
41_rand17.txt WA
41_rand18.txt WA
41_rand19.txt WA
41_rand20.txt WA
41_rand21.txt WA
41_rand22.txt WA
41_rand23.txt WA
41_rand24.txt WA