Submission #1014126

---

Source Code Expand

#include <iostream>
#include <complex>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;

typedef complex<double> Point;
typedef pair<Point, Point> Line;
	

void reverse(vector<Point> &p) {
	vector<Point> q;
	for (int i = (int)p.size() - 1; i >= 0; i--) q.push_back(p[i]);
	p = q;
}

double area(vector<Point> p) {
	double ret = 0;
	int i;
	
	for (i = 0; i < p.size() - 1; i++) {
		ret += (p[i].real() - p[i+1].real()) * (p[i].imag() + p[i+1].imag());
	}
	ret += (p[i].real() - p[0].real()) * (p[i].imag() + p[0].imag());
	return ret / 2;
}

double circum(vector<Point> p) {
	double ret = 0;
	int i;
	
	for (i = 0; i < p.size(); i++) {
		ret += abs(p[(i + 1) % p.size()] - p[i]);
	}
	return ret;
}

double cross(Point a, Point b) {
	return imag(conj(a) * b);
}

Point cross_point(Point a, Point b, Point c, Point d) {
	double A = cross(b - a, d - c);
	double B = cross(b - a, b - c);
	double eps = 1e-12;
	
	if (abs(A) < eps && abs(B) < eps) return c;
	if (abs(A) < eps) assert(false);
	return c + B / A * (d - c);
}

void move(Line &l, double dist) {
	Point trans = Point(0, 1) * (l.second - l.first); trans /= abs(trans);
	trans *= dist;
	
	l.first += trans;
	l.second += trans;
}

vector<Point> small_poly(vector<Point> p, double dist) {
	vector<Line> lines;
	vector<Point> poly;
	
	for (int i = 0; i < p.size(); i++) {
		lines.push_back(Line(p[i], p[(i + 1) % p.size()]));
	}
	
	for (int i = 0; i < p.size(); i++) {
		move(lines[i], dist);
	}
	
	for (int i = 0; i < p.size(); i++) {
		Point crs = cross_point(lines[i].first, lines[i].second, lines[(i+1) % p.size()].first, lines[(i+1) % p.size()].second);
		poly.push_back(crs);
	}
	return poly;
}

double max_length(vector<Point> p) {
	double ret = 0;
	int i;
	
	for (i = 0; i < p.size(); i++) {
		ret = max(ret, abs(p[(i + 1) % p.size()] - p[i]));
	}
	return ret;
}

int main() {
	double x, y;
	vector<Point> p; p.resize(3);
	
	cin >> x >> y; p[0] = Point(x, y);
	cin >> x >> y; p[1] = Point(x, y);
	cin >> x >> y; p[2] = Point(x, y);
	if (area(p) < 0) { reverse(p); }
	
	double st = 0;
	double ed = area(p) / circum(p) * 2;
	double mid;
	
	for (int i = 0; i < 100; i++) {
		mid = (st + ed) / 2;
		
		vector<Point> poly = small_poly(p, mid);
		//cout << mid << " " << area(poly) << " " << max_length(poly) << endl;
		if (max_length(poly) >= 2 * mid) { st = mid; }
		else { ed = mid; }
	}
	
	printf("%.14f\n", st);
	return 0;
}

Submission Info

Judge Result