学习心得(code)

superlong@CoreCoder

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

公告

文字可能放在http://blog.csdn.net/superlong100,此处存放代码

常用链接

留言簿(4)

我参与的团队

搜索

  •  

最新随笔

最新评论

  • 1. re: Poj 1279
  • 对于一个凹多边形用叉积计算面积 后能根据结果的正负来判断给的点集的时针方向?
  • --bsshanghai
  • 2. re: Poj 3691
  • 你写的这个get_fail() 好像并是真正的get_fail,也是说fail指向的串并不是当前结点的子串。为什么要这样弄呢?
  • --acmer1183
  • 3. re: HDU2295[未登录]
  • 这个是IDA* 也就是迭代加深@ylfdrib
  • --superlong
  • 4. re: HDU2295
  • 评论内容较长,点击标题查看
  • --ylfdrib
  • 5. re: HOJ 11482
  • 呵呵..把代码发在这里很不错..以后我也试试...百度的编辑器太烂了....
  • --csuft1

阅读排行榜

评论排行榜

#include <iostream>
#include 
<math.h>
#include 
<string.h>
#define eps 1e-7

using namespace std;

struct point{
    
double x, y;
    
void read(){scanf("%lf %lf"&x, &y);}
    
void write(){printf("%.2lf %.2lf\n", x, y);}
    point 
operator-(point &a)
    {
        point t;
        t.x 
= x - a.x;
        t.y 
= y - a.y;
        
return t;
    }
    point 
operator+(point &a)
    {
        point t;
        t.x 
= x + a.x;
        t.y 
= y + a.y;
        
return t;
    }
};

int n;
point p[
105];

double dist(point a, point b)
{
    point c 
= a - b;
    
return sqrt( c.x * c.x + c.y * c.y);
}

bool flag;

double xmul(point a, point b, point c)
{
return (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);}

point intersection(point u1, point u2,point v1, point v2)
{
    point ret 
= u1;
    
double t = ((u1.x - v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
                
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x 
+= (u2.x - u1.x) * t;
    ret.y 
+= (u2.y - u1.y) * t;
    
return ret;
}


point change(point a, point b, point next, 
double L)
{
    point t;
    t.x 
= -(b - a).y;
    t.y 
= (b - a).x;
    
double len = sqrt(t.x * t.x + t.y * t.y);
    t.x 
/= len;        t.y /= len;
    t.x 
*= L; t.y *= L;
    t 
= t + next;
    
return t;
}

int jud(double h)
{
    point tp[
105], tt[105], ns, ne, s, e, pp ;
    
int len = 0, tlen, i, j;

    
for(i = 0; i <= n; i ++) tp[i] = p[i];
    len 
= n;
    
    
for(i = 0; i < n; i ++)
    {
        s 
= change(p[i], p[i + 1], p[i], h);
        e 
= change(p[i], p[i + 1], p[i + 1], h); 
        
//        s.write();
//        e.write();
        
        tlen 
= 0;
        
for(j = 0; j < len; j ++)
        {
            ns 
= tp[j];    ne = tp[j + 1];
            
if(xmul(s, e, ns) <= 0)
                tt[tlen 
++= ns;
            
if(xmul(s, e, ns) * xmul(s, e, ne) < 0)
            {
                pp 
= intersection(s, e, ns, ne);
                
                tt[tlen 
++= pp;
            }    
        }
        tt[tlen] 
= tt[0];
        
for(j = 0; j <= tlen; j ++
        {
            tp[j] 
= tt[j];
//            printf("point:   ");
//            tp[j].write();
        }
        len 
= tlen;
//        printf("%d\n", len);
    }
    
return len;
}

double bsearch(double left, double right)
{    
    
while(right-left>eps)
    {
        
double mid=(left+right)/2;
//        printf("%lf %lf %lf:\n", left, mid, right);
        if(jud(mid))left=mid;
        
else          right=mid;
    }
    
return left; 

    
}

int main()
{
    
while(scanf("%d"&n), n)
    {
        
for(int i = 0; i < n; i ++)
            p[i].read();    
        p[n] 
= p[0];
        
double minn = -1, maxx = -1;
        
for(int i = 0; i < n; i ++)
        
for(int j = i + 1; j < n; j ++)
        {
            
double dis = dist(p[i], p[j]) / 2;
            
if(dis < minn || minn < eps)
                minn 
= dis;
            
if(dis > maxx || maxx < eps)
                maxx 
= dis;
        }
        flag 
= 0;
        
//printf("%.2lf  %.2lf\n", minn, maxx); while(1);
        double ans = bsearch(0, maxx);
        printf(
"%.6lf\n", ans);
    }
}

posted on 2009-09-18 21:10 superlong 阅读(464) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理