Submission #3058566

---

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;

	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 Info

Judge Result