結果
問題 | No.461 三角形はいくつ? |
ユーザー |
![]() |
提出日時 | 2016-12-15 04:02:03 |
言語 | D (dmd 2.109.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,246 bytes |
コンパイル時間 | 1,433 ms |
コンパイル使用メモリ | 149,480 KB |
実行使用メモリ | 9,628 KB |
最終ジャッジ日時 | 2024-06-12 05:34:42 |
合計ジャッジ時間 | 8,308 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 1 TLE * 1 -- * 39 |
ソースコード
import std.algorithm;import std.array;import std.ascii;import std.container;import std.conv;import std.math;import std.numeric;import std.range;import std.stdio;import std.string;import std.typecons;void log(A...)(A arg) { stderr.writeln(arg); }int size(T)(in T s) { return cast(int)s.length; }immutable real EPS = 1e-7;struct Point {real x, y;Point opBinary(string op)(in Point p) const if (op == "+" || op == "-") {return Point(mixin("x" ~ op ~ "p.x"), mixin("y" ~ op ~ "p.y"));}Point opBinary(string op)(real k) const if (op == "*" || op == "/") {return Point(mixin("x" ~ op ~ "k"), mixin("y" ~ op ~ "k"));}};real dot(in Point a, in Point b) { return a.x * b.x + a.y * b.y; }real cross(in Point a, in Point b) { return a.x * b.y - a.y * b.x; }real norm(in Point a) { return sqrt(dot(a, a)); }Point rot90(in Point p) { return Point(-p.y, p.x); }real angle(in Point a) { return atan2(a.y, a.x); }int ccw(Point a, Point b, Point c){b = b - a; c = c - a;if (cross(b, c) > EPS) return +1; // a,b,cの順に反時計周りif (cross(b, c) < -EPS) return -1; // a,b,cの順に時計周りif (dot(b, c) < 0) return +2; // c--a--b 直線if (norm(b) < norm(c)) return -2; // a--b--c 直線return 0; // a--c--b 直線}struct Line {Point a, b;};bool contains(in Line l, in Point p) { return ccw(l.a, l.b, p) % 2 == 0; }bool parallel(in Line s, in Line t) { return abs(cross(s.b - s.a, t.b - t.a)) < EPS; }bool orthogonal(in Line s, in Line t) { return abs(dot(s.b - s.a, t.b - t.a)) < EPS; }bool equals(in Line s, in Line t) { return parallel(s, t) && contains(s, t.a); }Point crosspoint(in Line s, in Line t) {real d = cross(t.b - t.a, s.b - s.a);assert(abs(d) >= EPS);return s.a + (s.b - s.a) * cross(t.b - t.a, t.b - s.a) / d;}Point projection(in Line l, in Point p) {Point u = (p - l.a), v = (l.b - l.a);return l.a + (v / norm(v)) * (dot(u, v) / norm(v));}Point reflection(in Line l, in Point p) {Point h = projection(l, p);return p + (h - p) * 2;}struct Segment {Point a, b;};bool intersects(in Segment s, in Segment t) {return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;}bool contains(in Segment s, in Point p) {return ccw(s.a, s.b, p) == 0;}real dist(in Segment s, in Point p) {Point q = projection(Line(s.a, s.b), p);auto t = Segment(p, q);if (intersects(s, t)) return norm(t.b - t.a);return min(norm(s.a - p), norm(s.b - p));}real dist(in Segment s, in Segment t) {if (intersects(s, t)) return 0;return min( min(dist(s, t.a), dist(s, t.b)),min(dist(t, s.a), dist(t, s.b)) );}void main() {auto N = readln.chomp.to!int;real[] Y;auto S = new Segment[][2];foreach (i; 0 .. N) {int p; real a, b; readf("%s %s %s\n",&p, &a, &b);if (p == 0) {Y ~= b / (a + b);} else {p--;Point s, t;if (p == 0) {s.x = (a / 2) / (a + b);s.y = a / (a + b);t.x = a / (a + b);t.y = 0;} else {s.x = (a / 2 + b) / (a + b);s.y = a / (a + b);t.x = b / (a + b);t.y = 0;}S[p] ~= Segment(s, t);}}Y ~= 0;S[0] ~= Segment(Point(0.5, 1), Point(1, 0));S[1] ~= Segment(Point(0.5, 1), Point(0, 0));int count(real sy, real ty) {int c = 0;foreach (y; Y) {if (sy <= y && y <= ty) c++;}return c;}//log(S);int ans = 0;foreach (s; S[0]) {foreach (t; S[1]) {if (! s.intersects(t)) continue;Point c = crosspoint(cast(Line)s, cast(Line)t);//log(c);real sy = max(s.b.y, t.b.y);real ty = min(s.a.y, t.a.y);ans += count(sy, c.y - EPS) + count(c.y + EPS, ty);}}writeln(ans);}