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 |
|
|
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 |