哎怎么说,感觉现在处理平面上点线的题已经比较熟练了。

这题就离散化然后搞个前缀和就没了。

准备开始进一步的自闭了。

下面是disguss的一些样例。。。

其实是我自己写错了个地方,本来能1A的。

 #include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
typedef double db;
const db eps=1e-;
const db pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
db abs(){ return sqrt(x*x+y*y);}
};
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
point getLL(point k1,point k2,point k3,point k4){
db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2);
}
int intersect(db l1,db r1,db l2,db r2){
if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2); return cmp(r1,l2)!=-&&cmp(r2,l1)!=-;
}
int checkSS(point k1,point k2,point k3,point k4){
return intersect(k1.x,k2.x,k3.x,k4.x)&&intersect(k1.y,k2.y,k3.y,k4.y)&&
sign(cross(k3-k1,k4-k1))*sign(cross(k3-k2,k4-k2))<=&&
sign(cross(k1-k3,k2-k3))*sign(cross(k1-k4,k2-k4))<=;
}
struct line{
point p[];
line(point k1,point k2){p[]=k1; p[]=k2;}
};
double l,r,y;
point p[];
int n;
point s1,t1,s2,t2;
//离散化+前缀和。
vector<db> v,a,b;
int pre[];
int main(){
ios::sync_with_stdio(false);
cout<<fixed<<setprecision();
while (cin>>l>>r>>y&&(l||r||y)){
s1={l,y};t1={r,y};
cin>>l>>r>>y;
s2={l,y};t2={r,y};
v.push_back(l);
v.push_back(r);
cin>>n;
for(int i=;i<=*n;i+=){
cin>>l>>r>>y;
p[i]={l,y};
p[i+]={r,y};
}
for(int i=;i<=*n;i+=){
if(cmp(s1.y,p[i].y)==&&cmp(p[i].y,s2.y)==){//在中间
point tmp = getLL(t1,p[i],s2,t2);
v.push_back(tmp.x);//-1
a.push_back(tmp.x);
tmp = getLL(s1,p[i+],s2,t2);
v.push_back(tmp.x);//+1
b.push_back(tmp.x);
}
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=;i<a.size();i++){
int id = lower_bound(v.begin(),v.end(),a[i])-v.begin();
pre[id]--;
}
for(int i=;i<b.size();i++){
int id = lower_bound(v.begin(),v.end(),b[i])-v.begin();
pre[id]++;
}
int id1 = lower_bound(v.begin(),v.end(),s2.x)-v.begin();
int id2 = lower_bound(v.begin(),v.end(),t2.x)-v.begin();
for(int i=;i<v.size();i++){
pre[i]+=pre[i-];
}
db ans = ;
for(int l=id1,r;l<=id2;l=r+){
r=l;
while (r<id2&&pre[r]>=)
r++;
ans=max(ans,v[r]-v[l]);
}
if(cmp(ans,0.00)==){
cout<<"No View"<<endl;
} else {
cout << ans << endl;
}
v.clear();
a.clear();
b.clear();
memset(pre,, sizeof(pre));
}
}
/**
2 6 6
0 15 0
1
2 6 7 2 6 6
0 15 0
1
2 6 7
2 6 6
0 15 0
1
4 4.5 5.5
2 6 6
0 15 0
16
0 1 3
1.5 2 3
2.5 3 3
3.5 4 3
4.5 5 3
5.5 6 3
6.5 7 3
7.5 8 3
8.5 9 3
9.5 10 3
10.5 11 3
11.5 12 3
12.5 13 3
13.5 14 3
14.5 15 3
15.5 16 3
2 6 6
0 15 0
16
0 1 .1
1.5 2 .1
2.5 3 .1
3.5 4 .1
4.5 5 .1
5.5 6 .1
6.5 7 .1
7.5 8 .1
8.5 9 .1
9.5 10 .1
10.5 11 .1
11.5 12 .1
12.5 13 .1
13.5 14 .1
14.5 15 .1
15.5 16 .1
2 6 6
0 15 0
14
0 1 3
1.5 2 3
2.5 3 3
3.5 4 3
4.5 5 3
5.5 6 3
8.5 9 3
9.5 10 3
10.5 11 3
11.5 12 3
12.5 13 3
13.5 14 3
14.5 15 3
15.5 16 3 2 6 6
0 15 1
5
1 1.5 6
17 18 1
3 5 3
0 20 10
0 20 0.5
*/

最新文章

  1. gedit 没有preference项,使preference回归,并用命令行设置行号,text wrapping等
  2. winform下自绘提示框风格窗体
  3. sql: sq_helptext
  4. SQL数据库基本语句
  5. 海康、大华IpCamera RTSP地址和格式
  6. PHP 文件上传功能
  7. HTML&amp;CSS基础学习笔记1.6-html的文本操作标签
  8. HTTPS那些事(一) HTTPS原理
  9. property、synthesize、id
  10. php soap调用asp.net webservice
  11. jquery背景动画插件使用
  12. 解析xml的问题未解决
  13. CSS.03 -- 浏览器行高、字体;盒子模型--边框、内边距、外边距
  14. HackerRank-Python攻城歷程-1.Tuples
  15. 利用正则表达式实现python强口令检测
  16. SQL Server 一张图让你秒懂联合表查询
  17. Windows下的Hadoop安装(本地模式)
  18. 2.1博客系统 |基于form组件和Ajax实现注册登录
  19. codeforce864d
  20. hdu 5073 有坑+方差贪心

热门文章

  1. openjdk for window
  2. Error-MVC: “/”应用程序中的服务器错误。
  3. linux下gflags的安装
  4. 关闭pycharm自动更新
  5. Activity class {com.../com....MainActivity} does not exist.
  6. 微信支付 python版
  7. App安全
  8. SQL Server 性能优化实战系列(一)
  9. 全面理解Java内存模型(JMM)及volatile关键字(转载)
  10. Apache-配置、测试和调试