結果
| 問題 | No.306 さいたま2008 |
| ユーザー |
 snuke
|
| 提出日時 | 2015-11-27 22:32:40 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 7,654 bytes |
| コンパイル時間 | 1,040 ms |
| コンパイル使用メモリ | 99,884 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2025-02-14 12:08:27 |
| 合計ジャッジ時間 | 1,962 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
ソースコード
#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 lineres[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 lineres[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);}};// geomint 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;}