Submission #1021928
Source Code Expand
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
//const int INF=5e8;
const double PI=acos(-1.0);
typedef complex<double> P;
namespace std {
bool operator < (const P& a, const P& b) {
return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
}
double cross(const P& a, const P& b) {
return imag(conj(a)*b);
}
double cross(const P& a,const P& b,const P& c){
return cross(b-a,c-a);
}
double dot(const P& a, const P& b) {
return real(conj(a)*b);
}
P rotate(const P& a,double ang){
return P(a.real()*cos(ang)-a.imag()*sin(ang),
a.real()*sin(ang)+a.imag()*cos(ang));
}
const double EPS=1e-9 ,EPS2 = 1e-9;
int sign(double a){
if(abs(a)<=EPS) return 0;
if(a>0) return 1;
return -1;
}
int ccw(P a, P b, P c) {
b -= a; c -= a;
if (cross(b, c) > EPS2) return +1; // counter clockwise
if (cross(b, c) < EPS2) return -1; // clockwise
return 0;
}
bool intersectLL(const P& l1,const P& l2, const P& m1, const P& m2) {
return abs(cross(l2-l1, m2-m1)) > EPS || // non-parallel
abs(cross(l2-l1, m1-l1)) == 0; // same line
}
bool intersectLS(const P& l1,const P& l2, const P& s1,const P& s2) {
return sign(cross(l2-l1, s1-l1))* // s[0] is left of l
sign(cross(l2-l1, s2-l1)) <= EPS; // s[1] is right of l
}
inline bool intersectLP(const P& l1,const P& l2, const P &p) {
return abs(cross(l2-p, l1-p)) <= EPS ;
}
inline bool intersectSS(const P& s1,const P& s2,const P& t1 ,const P& t2) {
return sign(cross(s1,s2,t1))*sign(cross(s1,s2,t2)) <= 0 &&
sign(cross(t1,t2,s1))*sign(cross(t1,t2,s2)) <= 0;
}
bool intersectSP(const P& s1,const P& s2, const P &p) {
if(abs(abs(s1-p)+abs(s2-p)-abs(s1-s2))<EPS) return true;
return false;
}
P projection(const P& l1,const P& l2, const P &p) {
double t = dot(p-l1, l1-l2) / norm(l1-l2);
return l1 + t*(l1-l2);
}
P reflection(const P &l1,const P& l2, const P &p) {
return p + 2.0 * (projection(l1,l2, p) - p);
}
double distanceLP(const P &l1,const P& l2, const P &p) {
return abs(p - projection(l1,l2, p));
}
double distanceLL(const P &l1,const P& l2, const P &m1,const P& m2) {
return intersectLL(l1,l2, m1,m2) ? 0 : distanceLP(l1,l2, m1);
}
double distanceLS(const P &l1,const P& l2, const P &s1,const P& s2) {
if (intersectLS(l1,l2, s1,s2)) return 0;
return min(distanceLP(l1,l2, s1), distanceLP(l1,l2,s2));
}
double distanceSP(const P &s1,const P& s2, const P &p) {
const P r = projection(s1,s2, p);
if (intersectSP(s1,s2, r)) return abs(r - p);
return min(abs(s1 - p), abs(s2 - p));
}
double distanceSS(const P &s1,const P& s2, const P &t1,const P& t2) {
if (intersectSS(s1,s2, t1,t2)) return 0;
return min(min(distanceSP(s1,s2, t1), distanceSP(s1,s2, t2)),
min(distanceSP(t1,t2, s1), distanceSP(t1,t2, s2)));
}
//instersectLL : true
P crosspointLL(const P &l1,const P& l2, const P &m1,const P& m2) {
double A = cross(l2 - l1, m2 - m1);
double B = cross(l2 - l1, l2 - m1);
if (abs(A) < EPS && abs(B) < EPS) return m1; // same line
if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
return m1 + B / A * (m2 - m1);
}
P input(){
double a,b;cin>>a>>b;
return P(a,b);
}
P p[3];
double solve(){
double a=abs(p[1]-p[0]);
P d1=p[1]/abs(p[1]),d2=p[2]/abs(p[2]);
P p1=P(0,0),p2=d1+d2;
d1=-p[1]/abs(p[1]),d2=(p[2]-p[1])/abs(p[2]-p[1]);
P p3=p[1],p4=p3+d1+d2;
P inn=crosspointLL(p1,p2,p3,p4);
double h=inn.imag();
return h/(1+2*h/a);
}
void normalize(){
p[2]-=p[0];
p[1]-=p[0];
p[0]=P(0,0);
double th=arg(p[1]);
p[1]=rotate(p[1],-th);
p[2]=rotate(p[2],-th);
p[2].imag(abs(p[2].imag()));
}
int main(){
REP(i,3) p[i]=input();
double ans=0;
normalize();
chmax(ans,solve());
swap(p[0],p[2]);
normalize();
chmax(ans,solve());
swap(p[1],p[2]);
normalize();
chmax(ans,solve());
printf("%.10f\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Inscribed Bicycle |
User |
hogloid |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
4962 Byte |
Status |
AC |
Exec Time |
5 ms |
Memory |
384 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 |
5 ms |
384 KB |
001.txt |
AC |
3 ms |
256 KB |
002.txt |
AC |
3 ms |
256 KB |
003.txt |
AC |
3 ms |
256 KB |
004.txt |
AC |
3 ms |
256 KB |
005.txt |
AC |
2 ms |
256 KB |
006.txt |
AC |
3 ms |
256 KB |
007.txt |
AC |
3 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 |
3 ms |
256 KB |
012.txt |
AC |
3 ms |
256 KB |
013.txt |
AC |
2 ms |
256 KB |
014.txt |
AC |
3 ms |
256 KB |
015.txt |
AC |
3 ms |
256 KB |
example0.txt |
AC |
4 ms |
384 KB |
example1.txt |
AC |
3 ms |
256 KB |