CODE FESTIVAL 2016 Grand Final(Parallel)

Submission #1678403

Source codeソースコード

// 基本テンプレート

#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) {
    double p = abs(b-c), q = abs(c-a), r = abs(a-b);
    return (p*a + q*b + r*c) / (p + q + r);
}

// 点 a1, a2 を通る直線と点 b との距離
double dist_lp(P a1, P a2, P b) {
    return abs( cross(a2-a1, b-a1) ) / abs(a2-a1);
}

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) {
        double dist = dist_lp(ps[i], ps[(i+1)%3], icpoint);
        chmin(mi, dist);
    }

    double ub = mi, lb = 0;
    rep(z,0,500) {
        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(GEQ(ma, 2*mid)) lb = mid;
        else ub = mid;
    }

    printf("%.12f\n", lb);
    return 0;
}

Submission

Task問題 B - Inscribed Bicycle
User nameユーザ名 Tsutajiro
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 500
Source lengthソースコード長 4655 Byte
File nameファイル名
Exec time実行時間 2 ms
Memory usageメモリ使用量 384 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0.txt,example1.txt
All 500 / 500 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
000.txt AC 2 ms 256 KB
001.txt AC 2 ms 256 KB
002.txt AC 2 ms 256 KB
003.txt AC 2 ms 256 KB
004.txt AC 2 ms 256 KB
005.txt AC 2 ms 256 KB
006.txt AC 2 ms 256 KB
007.txt AC 2 ms 256 KB
008.txt AC 2 ms 256 KB
009.txt AC 2 ms 256 KB
010.txt AC 2 ms 256 KB
011.txt AC 2 ms 256 KB
012.txt AC 2 ms 384 KB
013.txt AC 2 ms 256 KB
014.txt AC 2 ms 256 KB
015.txt AC 2 ms 256 KB
example0.txt AC 2 ms 256 KB
example1.txt AC 2 ms 256 KB