Submission #1678338
Source Code Expand
#include <iostream>
#include <complex>
#include <cstdio>
#include <utility>
using namespace std;
typedef complex<double> P;
typedef pair<P,P> L;
#define X real()
#define Y imag()
double dot(P a, P b){
return a.X * b.X + a.Y * b.Y;
}
double cross(P a, P b){
return a.X * b.Y - a.Y * b.X;
}
L angle_bisector(P a, P b, P c){
//角abcをの二等分線
//a, b or b, cが一致するとゼロ徐算が発生しREになる
P p = b + (a-b)/abs(a-b) + (c-b)/abs(c-b);
return L(b,p);
}
P intersection(L a, L b){
//直線aと直線bの交点
return a.first + cross(b.second-b.first,a.first-b.first)/(-cross(b.second-b.first,a.second-b.first)+cross(b.second-b.first,a.first-b.first))*(a.second-a.first);
}
double p_to_s_dist(P a, L s){
/*
if(dot(s.second-s.first,a-s.first) >= 0 && dot(s.first-s.second,a-s.second) >= 0){
return abs(cross(s.first-s.second,a-s.second))/abs(s.first-s.second);
}
return min(abs(a-s.first), abs(a-s.second));
*/
return abs(cross(s.first-s.second,a-s.second))/abs(s.first-s.second);
}
int main(){
P p[3];
double x, y;
for(int i = 0; i < 3; ++i){
cin >> x >> y;
p[i] = P(x,y);
}
L bisectors[3];
for(int i = 0; i < 3; ++i){
bisectors[i] = angle_bisector(p[(i+2)%3],p[i],p[(i+1)%3]);
//cout << bisectors[i].first << " " << bisectors[i].second << endl;
}
P inner_center = intersection(bisectors[0],bisectors[1]);
double ans = 0.0;
for(int i = 0; i < 3; ++i){
P a = p[i], b = inner_center;
L l = L(p[i],p[(i+1)%3]);
//cout << l.first << " " << l.second << endl;;
//cout << bisectors[(i+1)%3].first << " " << bisectors[(i+1)%3].second << endl;
cout << "i = " << i << endl;
for(int j = 0; j < 10000; ++j){
//cout << "a, b = " << a << " " << b << endl;
P m = (a+b)/2.0;
double d1 = p_to_s_dist(m,l)*2;
P k = intersection(bisectors[(i+1)%3], L(m,m+p[(i+1)%3]-p[i]));
//cout << "m = " << m << " k = " << k << endl;
double d2 = abs(k-m);
if(d1 < d2){
a = m;
}else{
b = m;
}
}
ans = max(ans,p_to_s_dist((a+b)/2.0,l));
}
printf("%.12f\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Inscribed Bicycle |
User |
TAB |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2212 Byte |
Status |
WA |
Exec Time |
2 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 |
WA |
2 ms |
256 KB |
001.txt |
WA |
2 ms |
256 KB |
002.txt |
WA |
2 ms |
256 KB |
003.txt |
WA |
2 ms |
256 KB |
004.txt |
WA |
2 ms |
256 KB |
005.txt |
WA |
2 ms |
256 KB |
006.txt |
WA |
2 ms |
256 KB |
007.txt |
WA |
2 ms |
256 KB |
008.txt |
WA |
2 ms |
256 KB |
009.txt |
WA |
2 ms |
256 KB |
010.txt |
WA |
2 ms |
256 KB |
011.txt |
WA |
2 ms |
256 KB |
012.txt |
WA |
2 ms |
256 KB |
013.txt |
WA |
2 ms |
256 KB |
014.txt |
WA |
2 ms |
256 KB |
015.txt |
WA |
2 ms |
256 KB |
example0.txt |
WA |
2 ms |
256 KB |
example1.txt |
WA |
2 ms |
256 KB |