#442652 (C++17) No.306 さいたま2008

提出ソース

結果

問題	No.306 さいたま2008
ユーザー	f1b_maxbl00d
提出日時	2020-03-11 20:34:05
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	6,115 bytes
コンパイル時間	1,514 ms
コンパイル使用メモリ	132,760 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-16 00:23:24
合計ジャッジ時間	2,511 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	2 ms 6,820 KB
testcase_20	AC	3 ms 6,816 KB
testcase_21	AC	2 ms 6,820 KB
testcase_22	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> PDL;
typedef pair<LD, LD> PDD;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

template<class T>
void in(T& x) {
	cin >> x;
}

template<class T1, class T2>
void in(pair<T1, T2>& p) {
	in(p.first);
	in(p.second);
}

template<class T>
void in(vector<T>& v, LL st = -1, LL en = -1) {
	if (st == -1) {
		st = 0;
		en = v.size() - 1;
	}
	for (LL n = st; n <= en; n++) {
		in(v[n]);
	}
}

typedef complex<LD> Point;
const LD eps = 1e-8;
const LD pi = acos(-1.0);

//イコール
bool equal(Point a, Point b) {
	return (abs(a - b) < eps);
}

//内積
LD dot(Point a, Point b) {
	return real(conj(a) * b);
}

//外積
LD cross(Point a, Point b) {
	return imag(conj(a) * b);
}

//直線(2点保持)
struct Line {
	Point s, e;
};

//円(中心と半径)
struct Circle {
	Point p;
	LD r;
};

//三点の位置関係
//1 -> a,b,cが反時計回りの順に並ぶ
//-1 -> a,b,cが時計回りの順に並ぶ
//2 -> c,a,bの順に直線に並ぶ
//-2 -> a,b,cの順に直線に並ぶ
//0 -> a,c,bの順に直線に並ぶ
int threePointsPosition(Point a, Point b, Point c) {
	b -= a; c -= a;
	if (cross(b, c) > eps)return 1;
	if (cross(b, c) < -eps)return -1;
	if (dot(b, c) < 0)return 2;
	if (norm(b) < norm(c))return -2;
	return 0;
}

//二直線の交差判定(2直線のなす角!=0)
bool isis_ll(Line l, Line m) {
	return !equal(cross(l.e - l.s, m.e - m.s), 0);
}

//直線lと線分sの交差判定
//(線分の一端ともう一端が、直線を挟んで逆側にあればよい)
bool isis_ls(Line l, Line s) {
	return (cross(l.e - l.s, s.s - l.s) * cross(l.e - l.s, s.e - l.s) < eps);
}

//点が直線状に存在するかの判定
//(直線状2点にそれぞれ線を結び、なす角=0orπ)
bool isis_lp(Line l, Point p) {
	return(abs(cross(l.e - p, l.s - p)) < eps);
}

//点が線分上に存在するかの判定
//(線分の2点までの距離の和が線分の長さに等しければよい)
bool isis_sp(Line s, Point p) {
	return (abs(s.e - p) + abs(s.s - p) - abs(s.e - s.s) < eps);
}

//線分と線分の交差判定
bool isis_ss(Line s, Line t) {
	LL res1 = threePointsPosition(s.s, s.e, t.s) * threePointsPosition(s.s, s.e, t.e);
	LL res2 = threePointsPosition(t.s, t.e, s.s) * threePointsPosition(t.s, t.e, s.e);
	return (res1 <= 0 && res2 <= 0);
}

//点から直線に下ろす垂線の足
Point proj(Line l, Point p) {
	Point a = p - l.s, b = l.e - l.s;
	return l.s + (dot(a, b) / norm(b)) * b;
}

//直線と直線の交点
Point is_ll(Line s, Line t) {
	Point sv = s.e - s.s, tv = t.e - t.s;
	assert(cross(sv, tv) != 0);
	return s.s + sv * cross(tv, t.s - s.s) / cross(tv, sv);
}

LD dist_lp(Line l, Point p) {
	return abs(p - proj(l, p));
}

LD dist_ll(Line l, Line m) {
	return isis_ll(l, m) ? 0 : dist_lp(l, m.s);
}

LD dist_ls(Line l, Line s) {
	return isis_ls(l, s) ? 0 : min(dist_lp(l, s.s), dist_lp(l, s.e));
}

LD dist_sp(Line s, Point p) {
	Point r = proj(s, p);
	return isis_sp(s, r) ? abs(r - p) : min(abs(s.e - p), abs(s.s - p));
}

LD dist_ss(Line s, Line t) {
	if (isis_ss(s, t))return 0;
	return min({ dist_sp(s,t.s),dist_sp(s,t.e),dist_sp(t,s.s),dist_sp(t,s.e) });
}

istream& operator>>(istream& is, Point& p) {
	LD x, y;
	cin >> x >> y;
	p = Point(x, y);
	return is;
}

istream& operator>>(istream& is, Line& l) {
	Point a, b;
	cin >> a >> b;
	l = { a,b };
	return is;
}

LD degtorad(LL theta) {
	return theta * pi / 180;
}

LD radtodeg(LL theta) {
	return theta * 180 / pi;
}

//点Xを、点Cを中心に\theta rad回転
Point rotate(Point X, Point C, LD theta) {
	return (X - C) * Point(cosl(theta), sinl(theta)) + C;
}

//e^{i\theta }を返す
Point eitheta(LD theta) {
	return Point(cosl(theta), sinl(theta));
}

LD abs(Point p) {
	return sqrtl(p.real() * p.real() + p.imag() * p.imag());
}

//頂点が反時計回りに与えられている多角形
using Polygon = vector<Point>;

//三角形の面積
LD area(Point a, Point b, Point c) {
	return fabsl(cross(b - a, c - a)) / 2;
}

//多角形の面積
LD area(Polygon P) {
	LD ans = 0;
	for (LL n = 1; n < P.size() - 1; n++) {
		LL iscl = threePointsPosition(P[0], P[n], P[n + 1]);
		if (abs(iscl) != 1)continue;
		if (iscl == 1) {
			ans += area(P[0], P[n], P[n + 1]);
		}
		else {
			ans -= area(P[0], P[n], P[n + 1]);;
		}
	}
	return ans;
}

//多角形の凸性判定
bool isConvex(Polygon P) {
	for (LL n = 0; n < P.size(); n++) {
		if (threePointsPosition(P[n], P[(n + 1) % P.size()], P[(n + 2) % P.size()]) == -1) {
			return false;
		}
	}
	return true;
}

//多角形に対して点がどこにあるか
//0->内部 1->辺上 2->外部
LL isPointin(Polygon Poly, Point P) {
	bool in = false;
	for (LL i = 0; i < Poly.size(); i++) {
		Point a = Poly[i] - P;
		Point b = Poly[(i + 1) % Poly.size()] - P;
		if (a.imag() > b.imag())swap(a, b);
		if (a.imag() <= 0 && 0 < b.imag() && cross(a, b) < 0) in = !in;
		if (cross(a, b) == 0 && dot(a, b) <= 0) return 1;
	}
	return in ? 0 : 2;
}

template<>
void in(Point& p) {
	LD r, i;
	cin >> r >> i;
	p = { r,i };
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	Point A, B;
	cin >> A >> B;
	LD left = 0, right = 1000;
	for (LL t = 0; t < 100; t++) {
		LD c1 = (left * 2 + right) / 3;
		LD c2 = (left + right * 2) / 3;
		LD f1 = abs(A - Point(0, c1))+abs(B-Point(0,c1));
		LD f2 = abs(A - Point(0, c2)) + abs(B - Point(0, c2));
		if (f1 > f2)left = c1;
		else right = c2;
	}
	cout << setprecision(12) << (left + right) / 2 << "\n";
	return 0;
}

yukicoder

結果

テストケース

ソースコード