https://www.luogu.org/problemnew/show/P1663

给定山的性状，求一个最低点可以看见所有的地方。

就是半平面交。

粘贴全家福：

```cpp
#include
using namespace std;
typedef long long ll;

//不要输出-0.0之类的数

const double eps=1e-8;

const double inf=1e9;

const double pi=acos(-1.0); //小数点后15位精度，和atan2相同

//判断浮点数的符号

inline int cmp(double x) {

return (fabs(x)<eps)?0:((x>0.0)?1:-1);

}

inline double sqr(double x) {

return x*x;

}

struct Point {

double x,y;

Point() {};

Point(const double x,const double y):x(x),y(y) {};

friend Point operator+(const Point &a,const Point &b) {

    return Point(a.x+b.x,a.y+b.y);

}

friend Point operator-(const Point &a,const Point &b) {

    return Point(a.x-b.x,a.y-b.y);

}

friend Point operator*(const Point &p,const double k) {

    return Point(p.x*k,p.y*k);

}

friend Point operator*(const double k,const Point &p) {

    return Point(p.x*k,p.y*k);

}

friend Point operator/(const Point &p,const double k) {

    return Point(p.x/k,p.y/k);

}

inline double angle() {

    //返回向量的倾斜角，[-pi, pi]

    return atan2(y,x);

}

};

double det(const Point &a,const Point &b) {

return a.xb.y-a.yb.x;

}

double dot(const Point &a,const Point &b) {

return a.xb.x+a.yb.y;

}

//半平面交，O(nlogn)

vector halfplane_intersection(vector v) {

sort(v.begin(),v.end(),compare);

deque q;

deque ans;

q.push_back(v[0]);

int vs=v.size();

for(int i=1;i<vs;++i){

    if(cmp((v[i].second-v[i].first).angle()-(v[i-1].second-v[i-1].first).angle())==0)

        continue;

    while(!ans.empty()&&!satisfy(ans.back(),v[i])){

        ans.pop_back();

        q.pop_back();

    }

    while(!ans.empty()&&!satisfy(ans.front(),v[i])){

        ans.pop_front();

        q.pop_front();

    }

    ans.push_back(intersect_point(q.back(),v[i]));

    q.push_back(v[i]);

}

while(!ans.empty()&&!satisfy(ans.back(),q.front())){

    ans.pop_back();

    q.pop_back();

}

while(!ans.empty()&&!satisfy(ans.front(),q.back())){

    ans.pop_front();

    q.pop_front();

}

ans.push_back(intersect_point(q.back(),q.front()));

return vector<Point>(ans.begin(),ans.end());

}

void solve() {

int n;

scanf("%d",&n);

double x[5005],y[5005];

for(int i=1;i<=n;i++){

scanf("%lf%lf",&x[i],&y[i]);

}

vector hp;

hp.push_back(Halfplane(Point(x[1],inf),Point(x[1],y[1])));

hp.push_back(Halfplane(Point(x[n],y[n]),Point(x[n],inf)));

hp.push_back(Halfplane(Point(x[n],inf),Point(x[1],inf)));

for(int i=2;i<=n;i++){

hp.push_back(Halfplane(Point(x[i-1],y[i-1]),Point(x[i],y[i])));

}

/*for(int i=0;i<(int)hp.size();i++){

    printf("Point1 %d: (%.4f, %4f)\n",i+1,hp[i].first.x,hp[i].first.y);

    printf("Point2 %d: (%.4f, %4f)\n",i+1,hp[i].second.x,hp[i].second.y);

    puts("");

}*/

double ans=inf;

vector<Point> hpi=halfplane_intersection(hp);

int hs=hpi.size();

for(int i=0;i<hs;i++){

    //printf("Point %d: (%.4f, %4f)\n",i+1,hpi[i].x,hpi[i].y);

    ans=min(ans,hpi[i].y);

}

printf("%8f\n",ans);

}

int main() {

ifdef Yinku

freopen("Yinku.in","r",stdin);

endif // Yinku

solve();

return 0;

}

<details>

巴特西

洛谷 - P1663 - 山 - 半平面交

ifdef Yinku

endif // Yinku

最新文章

热门文章