Submission #3226937
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
ll c=a%i_7;
if(c>=0)return c;
else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;//10^12
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
////////////////////////////////////////
//double abs(double a){if(a>=0)return a;else return -a;}//もしCEしたらこれ試してみて
double EPS=1e-10;
//誤差を考慮して足し算を行う
double add(double a,double b){
if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;
return a+b;
}
//二次元ベクトル構造体
struct P{
double x,y;int pos;
P(){}
P(double x,double y):x(x),y(y){
}
P operator +(P p){
return P(add(x,p.x),add(y,p.y));
}
P operator -(P p){
return P(add(x,-p.x),add(y,-p.y));
}
P operator *(double d){
return P(x*d,y*d);
}
double dot(P p){//内積
return add(x*p.x,y*p.y);
}
double det(P p){//外積
return add(x*p.y,-y*p.x);
}
};
///////////////////////////////////////////////
double pi=3.1415926536;
P rotate(P p,P c,double theta){
P q;
q.x=c.x+(p.x-c.x)*cos(theta)-(p.y-c.y)*sin(theta);
q.y=c.y+(p.y-c.y)*cos(theta)+(p.x-c.x)*sin(theta);
if(abs(q.x)<0)q.x=0;
if(abs(q.y)<0)q.y=0;
return q;
}
struct line{
double a,b,c;
};
line ask(P p,P q){
line l;
l.a=q.y-p.y;
l.b=-(q.x-p.x);
l.c=p.y*q.x-p.x*q.y;
return l;
}
bool infer(line l,P p){
if(l.b==0)return true;
if((-l.c-l.a*p.x)/l.b>p.y)return true;
else return false;
}
double dis(line l,P p){
return abs(l.a*p.x+l.b*p.y+l.c)/sqrt(pow(l.a,2)+pow(l.b,2));
}
P p[5];
bool check(double r){
bool flag=false;
rep(i,0,2){
P a,b,c;
a=p[i];b=p[i+1];c=p[i+2];
a=a-c;
b=b-c;
c.x=0;c.y=0;
double theta;
if(abs(a.y)<EPS){
if(a.x>EPS){
theta=0;
}else{
theta=pi;
}
}else if(abs(a.x)<EPS){
if(a.y>EPS){
theta=pi/2;
}else{
theta=pi*3/2;
}
}else{
theta=atan(a.y/a.x);
}
a=rotate(a,c,-theta);//a.y=0;
b=rotate(b,c,-theta);
if(a.x<EPS){
a=a*-1;
b=b*-1;
}
if(b.y<EPS){
b.y=b.y*(-1);
}
if(a.x<0||b.y<0){
}
line l1,l2;
l1=ask(b,c);
l2=ask(b,a);
double L=0,R=a.x-2*r;
if(R<0)continue;
rep(i,0,50){
double m=(L+R)/2;
P s,t;
s.x=m;s.y=r;
t.x=m+2*r;t.y=r;
if(!infer(l1,s)){
if(!infer(l2,t))break;
else{
L=m;
}
}else if(!infer(l2,t)){
R=m;
}else{
if(dis(l1,s)>=r&&dis(l2,t)>=r){
flag=true;
break;
}else if(dis(l1,s)<=r){
R=m;
}else if(dis(l2,t)<=r){
L=m;
}else{
break;
}
}
}
}
return flag;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
rep(i,0,2){
cin>>p[i].x>>p[i].y;
}
rep(i,0,1)p[i+3]=p[i];
double s=0,t=1000;
rep(i,1,100){
double m=(s+t)/2;
if(check(m))s=m;
else t=m;
}
printf("%5.20lf\n",s);
return 0;
}
//ios::sync_with_stdio(false);cin.tie(0);
Submission Info
Submission Time |
|
Task |
B - Inscribed Bicycle |
User |
sugarrr |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3941 Byte |
Status |
WA |
Exec Time |
1 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 |
AC |
1 ms |
256 KB |
001.txt |
WA |
1 ms |
256 KB |
002.txt |
WA |
1 ms |
256 KB |
003.txt |
WA |
1 ms |
256 KB |
004.txt |
WA |
1 ms |
256 KB |
005.txt |
WA |
1 ms |
256 KB |
006.txt |
WA |
1 ms |
256 KB |
007.txt |
WA |
1 ms |
256 KB |
008.txt |
WA |
1 ms |
256 KB |
009.txt |
WA |
1 ms |
256 KB |
010.txt |
WA |
1 ms |
256 KB |
011.txt |
WA |
1 ms |
256 KB |
012.txt |
WA |
1 ms |
256 KB |
013.txt |
WA |
1 ms |
256 KB |
014.txt |
WA |
1 ms |
256 KB |
015.txt |
WA |
1 ms |
256 KB |
example0.txt |
AC |
1 ms |
256 KB |
example1.txt |
WA |
1 ms |
256 KB |