注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3775/2508]点和直线  

2015-01-29 10:57:37|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3775: 点和直线

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 89  Solved: 16
[Submit][Status]

Description

你需要实现以下3种操作:
1.       平面上加入一条直线;
2.       删除一条已加入的直线;
3.       求一个点到平面上所有直线距离平方和最小,你需要输出这个最小值。

Input

第1行包含一个整数N,表示了操作数目。接下来N行操作属于下列3种格式之一:
格式1: 0 x1 y1 x2 y2 。插入直线操作,插入一条过(x1, y1), (x2, y2)的直线,保证两点不重合,坐标为实数(最多两位小数)并且绝对值不超过100。
格式2: 1 k 。删除直线操作,删除第i次插入操作所插入的直线,保证已经被删除的直线不会再被删除(即任意2次操作k值均不同),并且k不大于之前插入操作的次数。
格式3: 2 。查询操作,查询所要求的最小值。

Output

输出行数等于查询操作的次数,每行输出每次查询操作所要求的最小值,保留两位小数

Sample Input

10
0 0.0 0.0 1.0 0.0
2
0 0 1 1 1
2
0 0 2 1 2
2
1 2
2
1 3
2

Sample Output

0.00
0.50
2.00
2.00
0.00

HINT

对于100%的数据,N ≤ 120000。

Solution


[BZOJ3775/2508]点和直线 - Trinkle - n+e
 

Code

/**************************************************************
    Problem: 3775
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:820 ms
    Memory:3620 kb
****************************************************************/
 
#include<cstdio>
int n,ch,i,j;
double A,B,C,D,E,F,x1,y1,x2,y2,d,x,y,a,b,c,eps=1e-8;
double fabs(double x){return x>0?x:-x;}
struct Da{double A,B,C;}f[120010];
double check(double x){return x<1e-9?0:x;}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&ch);
        if(ch==0)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2),i++,
            a=y1-y2,b=x2-x1,c=x2*y1-x1*y2,d=a*a+b*b,
            f[i]=(Da){a,b,c},
            A+=a*a/d,B+=2*a*b/d,C+=b*b/d,
            D+=2*a*c/d,E+=2*b*c/d,F+=c*c/d;
        }
        else if(ch==1)
        {
            scanf("%d",&j);
            a=f[j].A,b=f[j].B,c=f[j].C,d=a*a+b*b,
            A-=a*a/d,B-=2*a*b/d,C-=b*b/d,
            D-=2*a*c/d,E-=2*b*c/d,F-=c*c/d;
        }
        else
        {
            if(!i)printf("0.00\n");
            else
            {
                d=B*B-4*A*C;
                if(fabs(d)>eps)x=(2*C*D-B*E)/d,y=(2*A*E-B*D)/d;
                else
                {
                    a=2*A+B,b=B+2*C,c=D+E,x=y=0;
                    if(fabs(a)>eps)x=-c/a;
                    else if(fabs(b)>eps)y=-c/b;
                    else y=-D/B;
                }
                printf("%.2lf\n",check(fabs(A*x*x+B*x*y+C*y*y+D*x+E*y+F)));
            }
        }
    }
}
  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018