Submission #3877788
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
//--------geometry original ------------------
#define curr(PP, i) PP[i]
#define next(PP, i) PP[(i+1)%PP.size()]
#define diff(PP, i) (next(PP, i) - curr(PP, i))
#define X real()
#define Y imag()
typedef long long ll;
typedef pair<ll, ll> P;
const double EPS = 1e-12;
const double PI = acos(-1.0);
typedef complex<double> point;
namespace std {
bool operator < (const point& a, const point& b) {
return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
bool operator == (const point& a,const point& b) {
return (abs(a.real() - b.real()) < EPS && abs(a.imag() - b.imag()) < EPS);
}
}
struct circle {
point p; double r;
circle(){}
circle(const point &p, double r) : p(p), r(r) { }
};
struct segment : public vector<point> {
segment(const point &a, const point &b) {
push_back(a); push_back(b);
}
};
double cross(const point& a, const point& b) {
return imag(conj(a)*b);
}
double dot(const point& a, const point& b) {
return real(conj(a)*b);
}
/*
a → b で時計方向に折れて b → c
a → b で半時計方向に折れて b → c
a → b で逆を向いて a を通り越して b → c
a → b でそのまま b → c
a → b で逆を向いて b → c ( または b == c )
*/
int ccw(point a, point b, point c) {
b -= a; c -= a;
if (cross(b, c) > 0) return +1; // counter clockwise
if (cross(b, c) < 0) return -1; // clockwise
if (dot(b, c) < 0) return +2; // c--a--b on line
if (norm(b) < norm(c)) return -2; // a--b--c on line
return 0;
}
bool intersectLL(const segment &l, const segment &m) {
return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // non-parallel
abs(cross(l[1] - l[0], m[0] - l[0])) < EPS; // same line
}
bool intersectLS(const segment &l, const segment &s) {
return cross(l[1] - l[0], s[0] - l[0])* // s[0] is left of l
cross(l[1] - l[0], s[1] - l[0]) < EPS; // s[1] is right of l
}
bool intersectLP(const segment &l, const point &p) {
return abs(cross(l[1] - p, l[0] - p)) < EPS;
}
bool intersectSP(const segment &s, const point &p) {
return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; // triangle inequality
}
//端点の交差も考える
bool intersectSS(const segment &s, const segment &t) {
return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) <= 0 &&
ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) <= 0;
}
point projection(const segment &l, const point &p) {
double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
return l[0] + t*(l[0] - l[1]);
}
point reflection(const segment &l, const point &p) {
return p + 2. * (projection(l, p) - p);
}
double distanceLP(const segment &l, const point &p) {
return abs(p - projection(l, p));
}
double distanceLL(const segment &l, const segment &m) {
return intersectLL(l, m) ? 0 : distanceLP(l, m[0]);
}
double distanceLS(const segment &l, const segment &s) {
if (intersectLS(l, s)) return 0;
return min(distanceLP(l, s[0]), distanceLP(l, s[1]));
}
double distanceSP(const segment &s, const point &p) {
const point r = projection(s, p);
if (intersectSP(s, r)) return abs(r - p);
return min(abs(s[0] - p), abs(s[1] - p));
}
double distanceSS(const segment &s, const segment &t) {
if (intersectSS(s, t)) return 0;
return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}
double distancePP(const point &a,const point &b){
return abs(a-b);
}
//交点
point crosspoint(const segment &l, const segment &m) {
double A = cross(l[1] - l[0], m[1] - m[0]);
double B = cross(l[1] - l[0], l[1] - m[0]);
if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
if (abs(A) < EPS) return point(INF,INF); // !!!PRECONDITION NOT SATISFIED!!!
return m[0] + B / A * (m[1] - m[0]);
}
//凸包
vector<point> convex_hull(vector<point> ps) {
int n = ps.size(), k = 0;
sort(ps.begin(), ps.end());
vector<point> ch(2*n);
for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
for (int i = n-2, t = k+1;i >= 0; ch[k++] = ps[i--]) // upper-hull
while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
ch.resize(k - 1);
return ch;
}
/*多角形内包判定
OUT:0
ON:1
IN:2
*/
int contains(const vector<point>& Poly, const point& p) {
bool in = false;
for (int i = 0; i < Poly.size(); ++i) {
point a = curr(Poly, i) - p, b = next(Poly, i) - p;
if (imag(a) > imag(b)) swap(a, b);
if (imag(a) <= 0 && 0 < imag(b))
if (cross(a, b) < 0) in = !in;
if (cross(a, b) == 0 && dot(a, b) <= 0) return 1;
}
return in ? 2 : 0;
}
//見えるか(可視グラフ用)
bool block_off(const point &a, const point &b, const vector<point> &obj) {
point m = (a+b)/2.0;
bool on = false, in = false;
for (int j = 0; j < obj.size(); ++j) {
point c = curr(obj,j), d = next(obj,j);
if (imag(d) < imag(c)) swap(c, d);
if (cross(a-c,b-c) * cross(a-d,b-d) < 0 && // strictly intersect.
cross(c-a,d-a) * cross(c-b,d-b) < 0) return true;
if (cross(a-c,b-c) == 0 && dot(a-c,b-c) < 0) return true;
if (imag(c) <= imag(m) && imag(m) < imag(d)) // strictly contain.
if (cross(c-m,d-m) < 0) in = !in;
if (cross(c-m,d-m) == 0 && dot(c-m,d-m) <= 0) on = true;
}
return !on && in;
}
//面積
double area(const vector<point>& p) {
double A = 0;
for (int i = 0; i < p.size(); ++i)
A += cross(curr(p, i), next(p, i));
return A / 2.;
}
//角度足し算
double add_rad(double a,double b){
double ret = a + b;
if(ret > PI)ret -= 2 * PI;
return ret;
}
//なす角(vector)
double angle(const point &a,const point &b) {
auto tmp = abs(arg(a) - arg(b));
return min(tmp, 2 * PI - tmp);
}
double angle(const segment &s1,const segment &s2) {
return angle(s1[1] - s1[0], s2[1] - s2[0]);
}
//点の回転
point rotate(const point &p, double rad) {
double x = p.real() * cos(rad) - p.imag() * sin(rad);
double y = p.imag() * cos(rad) + p.real() * sin(rad);
return point(x, y);
}
//並行
bool isParallel(const point &a, const point &b){
return abs(cross(a,b)) < EPS;
}
bool isParallel(const segment &a, const segment &b){
return isParallel(a[1]-a[0], b[1]-b[0]);
}
//直行
bool isOrthogonal(const point &a,const point &b){
return abs(angle(a,b) - PI / 2) < EPS;
}
bool isOrthogonal(const segment &a,const segment &b){
return isOrthogonal(a[1]-a[0],b[1]-b[0]);
}
//凸包判定
bool isConvex(vector<point> poly){
int sz = poly.size();
REP(i,sz){
int tmp = ccw(poly[i],poly[(i+1)%sz],poly[(i+2)%sz]);
if(tmp == -1){
return false;
}
}
return true;
}
double convex_diameter(const vector<point> &pt) {
const int n = pt.size();
int is = 0, js = 0;
for (int i = 1; i < n; ++i) {
if (imag(pt[i]) > imag(pt[is])) is = i;
if (imag(pt[i]) < imag(pt[js])) js = i;
}
double maxd = norm(pt[is]-pt[js]);
int i, maxi, j, maxj;
i = maxi = is;
j = maxj = js;
do {
if (cross(diff(pt,i), diff(pt,j)) >= 0) j = (j+1) % n;
else i = (i+1) % n;
if (norm(pt[i]-pt[j]) > maxd) {
maxd = norm(pt[i]-pt[j]);
maxi = i; maxj = j;
}
} while (i != is || j != js);
return sqrt(maxd); /* farthest pair is (maxi, maxj). */
}
vector<point> convex_cut(const vector<point> P, const segment& l) {
vector<point> Q;
for (int i = 0; i < P.size(); ++i) {
point A = curr(P, i), B = next(P, i);
if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
if (ccw(l[0], l[1], A)*ccw(l[0], l[1], B) < 0)
Q.push_back(crosspoint(segment(A, B), l));
}
return Q;
}
int main() {
double x1,x2,x3,y1,y2,y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
point a(x1,y1);
point b(x2,y2);
point c(x3,y3);
double A = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
double B = sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
double C = sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));
double ma = max(A,max(B,C));
double R = abs(area({a,b,c})) * 2 / (A + B + C);
double l = 0.;
double r = 10000.;
REP(i,1000){
double mid = (l + r) / 2;
double tmp = (1. - mid / R) * ma;
if(tmp < 2 * mid)r = mid;
else l = mid;
}
cout << Decimal << l << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Inscribed Bicycle |
User |
seica |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
8906 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 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 |
AC |
1 ms |
256 KB |
002.txt |
AC |
1 ms |
256 KB |
003.txt |
AC |
1 ms |
256 KB |
004.txt |
AC |
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 |
AC |
1 ms |
256 KB |
009.txt |
AC |
1 ms |
256 KB |
010.txt |
AC |
1 ms |
256 KB |
011.txt |
AC |
1 ms |
256 KB |
012.txt |
AC |
1 ms |
256 KB |
013.txt |
AC |
1 ms |
256 KB |
014.txt |
AC |
1 ms |
256 KB |
015.txt |
AC |
1 ms |
256 KB |
example0.txt |
AC |
1 ms |
256 KB |
example1.txt |
AC |
1 ms |
256 KB |