Submission #1013552


Source Code Expand

#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

// geom
#include <cmath>
const double inf = 1e6;
const double PI = acos(-1.0);
inline double toRad(double deg){ return deg * PI / 180.0;}

struct V {
  double x, y;
  V(double x=0, double y=0):x(x),y(y){}
  V operator+(V t) { return V(x+t.x,y+t.y);}
  V operator-(V t) { return V(x-t.x,y-t.y);}
  V operator*(double t) { return V(x*t,y*t);}
  V operator/(double t) { return V(x/t,y/t);}
  double dot(V t) { return x*t.x + y*t.y;}
  double cross(V t) { return x*t.y - y*t.x;}
  double norm2() { return x*x + y*y;}
  double norm() { return sqrt(x*x + y*y);}
  V rev() { return V(-x,-y);}
  V normalize() { return V(x/norm(), y/norm());}
  V rotate90() { return V(-y,x);}
  V rotate(V a, double rad){
    return V(a.x + cos(rad)*(x-a.x) - sin(rad)*(y-a.y),
             a.y + sin(rad)*(x-a.x) + cos(rad)*(y-a.y));
  }
  bool operator<(V a)const { return abs(x - a.x) > eps ? x < a.x : y < a.y;}
  bool operator==(V a)const { return abs(x - a.x) < eps && abs(y - a.y) < eps;}
};

struct Line {
  V s, t;
  Line(V s=V(0,0), V t=V(0,0)):s(s),t(t){}
  V dir() { return t-s;}
  V normalize() { return dir().normalize();}
  double norm() { return dir().norm();}
  /* +1: s-t,s-p : ccw
   * -1: s-t,s-p : cw
   * +2: t-s-p
   * -2: s-t-p
   *  0: s-p-t */
  int ccw(V p) {
    if (dir().cross(p-s) > eps) return +1;
    if (dir().cross(p-s) < -eps) return -1;
    if (dir().dot(p-s) < -eps) return +2;
    if (dir().norm()+eps < (p-s).norm()) return -2;
    return 0;
  }
  Line operator+(V a) { return Line(s+a,t+a);}
  Line operator-(V a) { return Line(s-a,t-a);}
  bool touch(Line l) {
    int a = ccw(l.s)*ccw(l.t), b = l.ccw(s)*l.ccw(t);
    return !a || !b || (a == -1 && b == -1);
  }
  double distLP(V p) { return abs(dir().cross(p-s)/norm());}
  double distSP(V p) {
    if (dir().dot(p-s) < eps) return (p-s).norm();
    if (dir().rev().dot(p-t) < eps) return (p-t).norm();
    return distLP(p);
  }
  double distSS(Line l) {
    if(touch(l)) return 0;
    return min(min(distSP(l.s),distSP(l.t)),min(l.distSP(s),l.distSP(t)));
  }
  V proj(V p) {
    double a = (p-s).dot(dir())/dir().norm2();
    return s + dir()*a;
  }
  Line mid() {
    V p = (s+t)/2, q = dir();
    return Line(p, p+V(q.y,-q.x));
  }
  V xp(Line l) {
    V a = dir(), b = l.dir();
    if (abs(b.cross(a)) < eps) return V(inf,inf);
    return s + a*(b.cross(l.s-s)/b.cross(a));
  }
};

typedef vector<V> Poly;
inline V pnxt(Poly& p, int i) { return p[(i+1)%sz(p)];}
inline V ppre(Poly& p, int i) { return p[(i-1+sz(p))%sz(p)];}
inline Line pline(Poly& p, int i) { return Line(p[i],pnxt(p,i));}
// geom

Line gl(Poly p, double r) {
  Line l = pline(p,0);
  Line res = l-l.dir().rotate90().normalize()*r;
  // printf("%.02f %.02f %.02f %.02f\n",l.s.x,l.s.y,l.t.x,l.t.y);
  // printf("%.02f %.02f %.02f %.02f\n",res.s.x,res.s.y,res.t.x,res.t.y);
  return res;
}

bool f(Poly p, double r) {
  vector<Line> ls;
  rep(i,3) {
    ls.pb(gl(p,r));
    rotate(p.begin(),p.begin()+1,p.end());
  }
  ls.pb(ls[0]);
  double mx = 0;
  Poly ps;
  rep(i,3) {
    ps.pb(ls[i].xp(ls[i+1]));
  }
  // rep(i,3) printf("%.3f %.3f\n",ps[i].x,ps[i].y);
  // cout<<ls[0].ccw(ps[1])<<endl;
  if (ls[0].ccw(ps[1]) == 1) return false;
  ps.pb(ps[0]);
  rep(i,3) {
    maxs(mx, (ps[i]-ps[i+1]).norm());
  }
  return mx > r*2;
}

int main() {
  Poly p(3);
  rep(i,3) {
    cin >> p[i].x >> p[i].y;
  }
  if (pline(p,0).ccw(p[2]) == 1) reverse(rng(p));
  // f(p,0.1); return 0;
  double ans = 0;
  rep(ri,3) {
    double l = 0, r = 10000;
    rep(ti,100) {
      double c = (l+r)/2;
      if (f(p,c)) l = c; else r = c;
    }
    rotate(p.begin(),p.begin()+1,p.end());
    maxs(ans,l);
  }
  printf("%.10f\n",ans);
  return 0;
}





























Submission Info

Submission Time
Task B - Inscribed Bicycle
User snuke
Language C++14 (GCC 5.4.1)
Score 500
Code Size 5938 Byte
Status AC
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 18
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 3 ms 256 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 3 ms 256 KB
006.txt AC 3 ms 256 KB
007.txt AC 3 ms 256 KB
008.txt AC 3 ms 256 KB
009.txt AC 3 ms 256 KB
010.txt AC 3 ms 256 KB
011.txt AC 3 ms 256 KB
012.txt AC 3 ms 256 KB
013.txt AC 3 ms 256 KB
014.txt AC 3 ms 256 KB
015.txt AC 3 ms 256 KB
example0.txt AC 3 ms 256 KB
example1.txt AC 3 ms 256 KB