#60357 (C++11) No.306 さいたま2008

• 問題: No.306 さいたま2008
• ユーザー: snuke
• 提出日時: 2015-11-27 22:32:40
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 7,654 bytes
• コンパイル時間: 1,262 ms
• コンパイル使用メモリ: 95,660 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-13 23:27:41
• 合計ジャッジ時間: 1,942 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB

ソースコード

#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>
#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 snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
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':' ');}

const int MX = 100005, INF = 1000010000;
const ll LINF = 1000000000000000000ll;
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;
  }
  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())/(norm()*norm());
    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)%p.size()];}
inline V ppre(Poly& p, int i) { return p[(i-1+p.size())%p.size()];}
inline Line pline(Poly& p, int i) { return Line(p[i],pnxt(p,i));}
Poly conv(Poly a) {
  int n = a.size();
  if (n == 1) return a;
  sort(a.begin(),a.end());
  Poly res(n*2);
  int k = 0;
  for (int i = 0; i < n; ++i){
    while (k > 1 && Line(res[k-1],res[k-2]).ccw(a[i]) <= -1) --k; // != 1 to avoid line
    res[k++] = a[i];
  }
  int pre = k;
  for (int i = n - 2; 0 <= i; --i){
    while (k > pre && Line(res[k-1],res[k-2]).ccw(a[i]) <= -1) --k; // != 1 to avoid line
    res[k++] = a[i];
  }
  res.resize(k-1);
  return res;
}
double area(Poly& a) {
  double res = 0;
  rep(i,a.size()-2){
    res += abs(V(a[i+1]-a[0]).cross(V(a[i+2]-a[0])));
  }
  return res/2;
}
Poly convCut(Poly& a, Line b) {
  Poly g;
  rep(i,a.size()){
    if (b.ccw(a[i]) == 1) g.push_back(a[i]);
    Line l(a[i],pnxt(a,i));
    V x = b.xp(l);
    if (l.ccw(x) == 0 && !(a[i] == x)) g.push_back(x);
  }
  return g;
}
vector<Poly> voronoi(Poly& p, Poly& c) {
  vector<Poly> g;
  rep(i,p.size()) g.push_back(c);
  rep(i,p.size())rep(j,p.size()) {
    if (i == j) continue;
    Line l = Line(p[i],p[j]).mid();
    if (l.ccw(p[i]) != 1) swap(l.s,l.t);
    g[i] = convCut(g[i],l);
  }
  return g;
}

struct Circle {
  V o; double r;
  Circle(V o=V(0,0), double r=0):o(o),r(r){}
  Poly xp(Circle c) {
    Poly res;
    double d = (o-c.o).norm();
    if (d > r+c.r) return res;
    if (d+min(r, c.r) < max(r, c.r)+eps) return Poly();
    double rcos = (d*d + r*r - c.r*c.r) / (2.0*d);
    double rsin = sqrt(r*r - rcos*rcos);
    V a = (c.o-o).normalize();
    res.push_back(o + V(a.x*rcos - a.y*rsin, a.x*rsin + a.y*rcos));
    res.push_back(o + V(a.x*rcos + a.y*rsin, -a.x*rsin + a.y*rcos));
    return res;
  }
  Poly xp(Line l) {
    Poly res;
    double h = l.distLP(o);
    if (h > r+eps) return res;
    V p = l.proj(o);
    double d = sqrt(max(0.0, r*r-h*h));
    V q = l.normalize();
    res.push_back(p + q*d);
    res.push_back(p - q*d);
    return res;
  }
  bool in(V p) { return (p-o).norm() < r+eps;}
  bool touch(Circle c) { return (c.o-o).norm() < c.r+r+eps;}
  double distCC(Circle c) { return max((c.o-o).norm()-c.r-r, 0.0);}
  Poly tang(V p) {
    Poly res;
    double a = (p-o).norm2(), b = a-r*r;
    if (b < -eps) return res;
    b = max(b,0.0);
    V h = o + (p-o)*(r*r/a);
    V v = (p-o).rotate90()*(r*sqrt(b)/a);
    res.push_back(h+v);
    res.push_back(h-v);
    return res;
  }
  vector<Line> tangC(Circle c) {
    vector<Line> res;
    if (abs(r-c.r) < eps) {
      V v = (c.o-o).rotate90().normalize()*r;
      res.push_back(Line(o+v,c.o+v));
      res.push_back(Line(o-v,c.o-v));
    } else {
      V p = (o*-c.r + c.o*r) / (r-c.r);
      Poly a = tang(p), b = c.tang(p);
      rep(i,a.size())rep(j,b.size()) {
        if (abs(Line(a[i],b[j]).ccw(p)) == 2) res.push_back(Line(a[i],b[i]));
      }
    }
    V p = (o*c.r + c.o*r)/(r+c.r);
    Poly a = tang(p), b = c.tang(p);
    rep(i,a.size())rep(j,b.size()) {
      if (Line(a[i],b[j]).ccw(p) == 0) res.push_back(Line(a[i],b[i]));
    }
    return res;
  }
  double TriArea(V a, V b) {
    if (a == o || b == o) return 0;
    a = a-o; b = b-o;
    double d = a.cross(b)/2;
    if (a.norm() > r+eps || b.norm() > r+eps){
      double e = (atan2(a.y,a.x)-atan2(b.y,b.x))/(PI*2);
      while (e < 0) e += 1;
      while (e > 1) e -= 1;
      return r*r*PI * min(e,1-e) * (d<0?-1:1);
    }
    return d;
  }
  double PolyArea(Poly p) {
    double res = 0;
    rep(i,p.size()){
      V a = p[i], b = p[(i+1)%p.size()];
      Poly x = xp(Line(a,b));
      if (x.size() == 2 && (x[0]-a).norm() > (x[1]-a).norm()) swap(x[0],x[1]);
      Poly ps;
      ps.push_back(a);
      rep(j,x.size()) if (Line(a,b).ccw(x[j]) == 0) ps.push_back(x[j]);
      ps.push_back(b);
      rep(i,ps.size()-1) res += TriArea(ps[i],ps[i+1]);
    }
    return abs(res);
  }
};
// geom


int main() {
  V a, b;
  cin >> a.x >> a.y;
  cin >> b.x >> b.y;
  b.x *= -1;
  V x = Line(V(0,-100),V(0,10000)).xp(Line(a,b));
  printf("%.10f\n", x.y);
  return 0;
}