Submission #2852657
Source Code Expand
#include <iostream>
#include <stdio.h>
#include <math.h>
#define eps 1e-8
using namespace std;
struct vec2d{
double x, y;
vec2d(){}
vec2d(double x, double y){
this->x = x, this->y = y;
}
double add(double a, double b){
if(fabs(a+b) < eps * (fabs(a) + fabs(b))) return 0.0;
return a+b;
}
vec2d operator+(vec2d ope){
return vec2d(add(x, ope.x), add(y, ope.y));
}
vec2d operator-(vec2d ope){
return vec2d(add(x, -ope.x), add(y, -ope.y));
}
vec2d operator*(double t){
return vec2d(x*t, y*t);
}
vec2d operator/(double t){
return vec2d(x/t, y/t);
}
double dot(vec2d ope){
return add(x*ope.x, y*ope.y);
}
double cross(vec2d ope){
return add(x*ope.y, -y*ope.x);
}
double norm(){
double d2 = dot(*this);
if(d2 > 0) return sqrt(d2);
return 0.0;
}
};
double distPP(vec2d p, vec2d q){
return (p-q).norm();
}
vec2d p[3];
vec2d getcenter(int i, double r)
{
vec2d a, b;
a = p[(i+1)%3] - p[i], b = p[(i+2)%3] - p[i];
double th = acos(a.dot(b) / (a.norm() * b.norm()));
a = a / a.norm();
if(a.cross(b) < 0) b = vec2d(a.y, -a.x);
else b = vec2d(-a.y, a.x);
vec2d ret = p[i];
ret = ret + a * r / tan(th/2);
ret = ret + b * r;
return ret;
}
bool check(double r)
{
vec2d c[3];
for(int i = 0; i < 3; i++) c[i] = getcenter(i, r);
return distPP(c[0], c[1]) >= 2*r || distPP(c[1], c[2]) >= 2*r || distPP(c[2], c[0]) >= 2*r;
}
int main(void)
{
for(int i = 0; i < 3; i++){
cin >> p[i].x >> p[i].y;
}
double L = distPP(p[0], p[1]) + distPP(p[1], p[2]) + distPP(p[2], p[0]);
double S = fabs((p[1]-p[0]).cross(p[2]-p[0]) / 2);
double R = 2*S/L;
double ub = R, lb = 0, mid;
for(int i = 0; i < 100; i++){
mid = (ub + lb) * 0.5;
if(check(mid)) lb = mid;
else ub = mid;
}
printf("%.11f\n", (ub+lb)*0.5);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Inscribed Bicycle |
User |
leaf1415 |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
1861 Byte |
Status |
AC |
Exec Time |
2 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 |
2 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 |