1039 -- Pipe

  理解错题意一个晚上。_(:з」∠)_

  题意很容易看懂,就是要求你求出从外面射进一根管子的射线,最远可以射到哪里。

  正解的做法是,选择上点和下点各一个,然后对于每个折点位置竖直位置判断经过的点是否在管中。如果是,就继续找,如果不在管中,这时射线必然已经穿过管出去了,这时就要找射线和管上下壁的交点。

代码如下:

 #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath> using namespace std; const double EPS = 1e-;
const int N = ;
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
bool operator < (Point a) const { return sgn(x - a.x) < || sgn(x - a.x) == && y < a.y;}
bool operator == (Point a) const { return sgn(x - a.x) == && sgn(y - a.y) == ;}
Point operator + (Point a) { return Point(x + a.x, y + a.y);}
Point operator - (Point a) { return Point(x - a.x, y - a.y);}
Point operator * (double p) { return Point(x * p, y * p);}
Point operator / (double p) { return Point(x / p, y / p);}
} ;
typedef Point Vec;
inline double dot(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double cross(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double veclen(Vec x) { return sqrt(dot(x, x));}
inline Point vecunit(Vec x) { return x / veclen(x);}
inline Point normal(Vec x) { return Point(-x.y, x.x) / veclen(x);} struct Line {
Point s, t;
Line() {}
Line(Point s, Point t) : s(s), t(t) {}
Vec vec() { return t - s;}
Point point(double p) { return s + vec() * p;}
} ; Point up[N], dw[N];
Line ul[N], dl[N]; inline Point llint(Point P, Vec u, Point Q, Vec v) { return P + u * (cross(v, P - Q) / cross(u, v));}
bool tstcross(Point a, Point b, Point c, Point d) { return sgn(cross(a - c, b - c)) * sgn(cross(a - d, b - d)) > ;} double cal(Point s, Point t, int n) {
Line tl = Line(s, t);
if (tstcross(tl.s, tl.t, up[], dw[])) return -1e100;
for (int i = ; i < n - ; i++) {
if (tstcross(tl.s, tl.t, up[i + ], dw[i + ])) {
double ret = -1e100;
if (!tstcross(tl.s, tl.t, ul[i].s, ul[i].t)) {
Point tp = llint(tl.s, tl.vec(), ul[i].s, ul[i].vec());
ret = max(ret, tp.x);
}
if (!tstcross(tl.s, tl.t, dl[i].s, dl[i].t)) {
Point tp = llint(tl.s, tl.vec(), dl[i].s, dl[i].vec());
ret = max(ret, tp.x);
}
return ret;
}
}
return 1e100;
} void work(int n) {
for (int i = ; i < n - ; i++) {
ul[i] = Line(up[i], up[i + ]);
dl[i] = Line(dw[i], dw[i + ]);
}
double ans = -1e100;
for (int i = ; i < n; i++) {
for (int j = i + ; j < n; j++) {
if (ans >= 1e99) break;
ans = max(ans, cal(up[i], dw[j], n));
ans = max(ans, cal(dw[i], up[j], n));
}
}
if (ans >= 1e99) puts("Through all the pipe.");
else printf("%.2f\n", ans);
} int main() {
// freopen("in", "r", stdin);
int n;
while (~scanf("%d", &n) && n) {
for (int i = ; i < n; i++) {
scanf("%lf%lf", &up[i].x, &up[i].y);
dw[i] = Point(up[i].x, up[i].y - 1.0);
}
work(n);
}
return ;
}

——written by Lyon

最新文章

  1. jquery placeholder
  2. gcc编译命令行依赖库的指定顺序
  3. Mount挂载命令使用方法
  4. java中Collection类及其子类
  5. 【洛谷P1969】积木大赛
  6. XACT_ABORT 用法
  7. HTMLParser使用详解(3)- 通过Filter访问内容
  8. LFI &amp; RFI &amp; PHP封装协议之安全问题研究
  9. javascript 对象的复制
  10. linux系统编程之文件IO
  11. 14_Android中Service的使用,关于广播接收者的说明
  12. 用python-webdriver实现自动填表
  13. react 的进阶
  14. linux 网络设置
  15. Mike and palindrome CodeForces - 798A
  16. Java运算符和引用数据类型(Scanner、Random)
  17. Eclipes导入工程
  18. Python基础03_pycharm
  19. Markdown使用方法
  20. bash处理一条命令的步骤

热门文章

  1. centos部分网站无法访问问题的解决
  2. nginx源码分析线程池详解
  3. CSS(中)篇
  4. laravel-admin
  5. C# 通过URL得到图片的问题
  6. 【Leetcode 滑动窗口】顺次数(1291)
  7. Directx11教程(47) alpha blend(4)-雾的实现
  8. oracle-Mount
  9. PHPCMS快速建站系列之网站迁移(本地到服务器,服务器迁移,更换域名等)
  10. 如何在Liferay 7中创建一个简单的JSF Portlet