hdu--1077--Catching Fish

思路:

  1.枚举两点确定圆心,大于2不用考虑

  2.逐个判断判断距圆心的距离小于1.00001符合题意

这个题,主要在求圆心上废了不少功夫,但是仍存在问题

#include<iostream>
#include<cmath>
#include<vector>
#include<cstdio>
;
using namespace std;
struct point{
    double x,y;
    point():x(),y(){};
};
double getDistance(point,point);
point getCentral(point,point);
int main()
{
    int t;
    cin>>t;
    while(t--){
        vector<point> vec;
        int n;cin>>n;
        ;i<n;++i){
            point temp;
            cin>>temp.x>>temp.y;
            vec.push_back(temp);
        }
        ;//捕鱼数
        auto it=vec.begin();
        ;i<vec.size()-;++i,++it){
            auto iter=it;
            for(++iter;iter!=vec.end();++iter){
                point cen;//圆心
                if(getDistance((*it),(*iter)) >2.0)continue;
                cen = getCentral((*it),(*iter));
                ;
                for(auto p=vec.begin();p!=vec.end();++p){
                    if(getDistance(cen,(*p)) <= 1.0001)k++;
                }
                if(cut < k)cut=k;
            }
        }
        cout<<cut<<endl;
    }
    ;
}
double getDistance(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point getCentral(point a,point b){
    point o;
    point c;//a,b中点
    c.x=(a.x+b.x)/;
    c.y=(a.y+b.y)/;
    double l=getDistance(c,o);//oc长度
    );
    double len=sqrt(1.0-temp*temp);//圆心到直线AB的距离
    point central;
//    if(fabs(a.y-b.y)<eps){
//        central.x=c.x;
//        central.y=c.y+len;
//    }
//    else {//大牛考虑了两个点几乎重合的情况,按照题意不必考虑
        double ang=atan(-(a.x-b.x)/(a.y-b.y));
        central.x=c.x+cos(ang)*len;//cos*斜边长
        central.y=c.y+sin(ang)*len;//sin*斜边长
        /*
        最初自己用临边/斜边的方式模拟正余弦值,但是误差不小,
        甚至两点确定的圆,距离两点的距离大于1
        */
/*注意:这个圆心最后是用中点的坐标加上cos*斜边长,但是减去呢?明显不对了虽然A了,但枚举不是正确的方法*/
//     }
    return central;
}
上一篇:php利用淘宝IP库获取用户ip地理位置


下一篇:BZOJ2726: [SDOI2012]任务安排