Submission #1678389
Source Code Expand
// 基本テンプレート
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;
// xy平面上の点(ベクトル)を表現するには、complex型を利用するとよい
typedef complex<double> P;
// 辺の表現 (座標を2つ pair でもつ)
typedef pair<P, P> L;
// 円の表現 (座標 P と 半径 d で表現する)
typedef pair<P, double> C;
// 成分を取り出すのを簡単にする
#define X real()
#define Y imag()
// 誤差(epsilon)の定義
#define EPS (1e-10)
// 2つの要素が等しいかどうか
#define EQ(a,b) (abs((a) - (b)) < EPS)
// 2つのベクトルが等しいかどうか
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
// m は n より大きい(以上)かどうか
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
// m は n より小さい(以下)かどうか
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))
// 2つのベクトルの内積を求める
double dot(P a, P b) {
return (a.X * b.X + a.Y * b.Y);
}
// 2つのベクトルの外積を求める
double cross(P a, P b) {
return (a.X * b.Y - a.Y * b.X);
}
// ccw (c が直線(線分) ab に対してどのような位置関係か?)
// Verified: AOJ CGL_1_C: Counter-Clockwise
// +1 ... a → b で半時計方向に折れて b → c (COUNTER_CLOCKWISE)
// -1 ... a → b で時計方向に折れて b → c (CLOCKWISE)
// +2 ... c, a, b がこの順で同一直線状にある場合 (ONLINE_BACK)
// -2 ... a, b, c がこの順で同一直線状にある場合 ( or a == b ) (ONLINE_FRONT)
// 0 ... c が線分 ab 上にある場合 (点 a, b 上を含む) (ON_SEGMENT)
int ccw(P a, P b, P 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;
}
// 直線 a1, a2 と直線b1, b2の交点を求める
// Verified: AOJ CGL_2_C.cpp
P crossp_ll(P a1, P a2, P b1, P b2) {
double d1 = cross(b2-b1, b1-a1);
double d2 = cross(b2-b1, a2-a1);
if( EQ(d1,0) && EQ(d2,0) ) return a1; // same line
if( EQ(d2,0) ) assert(false); // precondition not satisfied
return a1 + d1 / d2 * (a2 - a1);
}
// 三角形の内心
P InnerCenter(P a, P b, P c) {
P x = abs(a) * a + abs(b) * b + abs(c) * c;
double y = abs(a) + abs(b) + abs(c);
return x / y;
}
P ps[3];
signed main() {
rep(i,0,3) {
double x, y; cin >> x >> y;
ps[i] = P(x, y);
}
int c = ccw(ps[0], ps[1], ps[2]);
double mi = INF;
P icpoint = InnerCenter(ps[0], ps[1], ps[2]);
rep(i,0,3) chmin(mi, abs(ps[i] - icpoint));
double ub = mi, lb = 0;
rep(z,0,100) {
double mid = (ub + lb) / 2;
vector<L> ls;
rep(i,0,3) {
P p = ps[i], q = ps[(i+1)%3];
P diff = q - p;
P ortho = P((-1)*c*diff.Y, c*diff.X);
ortho = ortho / abs(ortho);
ls.push_back(make_pair(p+mid*ortho, q+mid*ortho));
}
vector<P> isec;
rep(i,0,3) {
isec.push_back(crossp_ll(ls[i].first, ls[i].second, ls[(i+1)%3].first, ls[(i+1)%3].second));
}
double ma = 0;
rep(i,0,3) {
chmax(ma, abs(isec[(i+1)%3] - isec[i]));
}
if(ma >= 2*mid) lb = mid;
else ub = mid;
}
printf("%.12f\n", lb);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Inscribed Bicycle |
User |
tsutaj |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4482 Byte |
Status |
WA |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, example0.txt, example1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
1 ms |
256 KB |
001.txt |
WA |
1 ms |
256 KB |
002.txt |
AC |
1 ms |
256 KB |
003.txt |
AC |
1 ms |
256 KB |
004.txt |
WA |
1 ms |
256 KB |
005.txt |
AC |
1 ms |
256 KB |
006.txt |
AC |
1 ms |
256 KB |
007.txt |
AC |
1 ms |
256 KB |
008.txt |
WA |
1 ms |
256 KB |
009.txt |
AC |
1 ms |
256 KB |
010.txt |
WA |
1 ms |
256 KB |
011.txt |
AC |
1 ms |
256 KB |
012.txt |
WA |
1 ms |
256 KB |
013.txt |
AC |
1 ms |
256 KB |
014.txt |
WA |
1 ms |
256 KB |
015.txt |
WA |
1 ms |
256 KB |
example0.txt |
AC |
1 ms |
256 KB |
example1.txt |
AC |
1 ms |
256 KB |