hoj第三场G-manhattanp ositioning system

---恢复内容开始---

一、题意

在二维坐标系内，给定若干个点和目标点距离该点的曼哈顿距离，求是否存在唯一解使得目标点坐标为整数。

二、题解

重新思考题目模型，考虑曼哈顿距离一定时，几何含义为，以给定点为中心，以二倍曼哈顿距离为对角线的矩形的轮廓线。则原题可以理解为，寻找唯一的被所有矩形覆盖的整数点。

于是，考虑扫描线思路，首先将所有涉及到的坐标离散化并标记出来，其次建立线段树，用于统计某个区间出现的最多的点的次数。则，nodes[0]中保存着当前各个节点最大覆盖次数。当覆盖次数为n时，必然存在实数解，但是不一定存在整数解。

考虑模型实际上在y轴上推进，x轴上做统计。考虑到几何意义，则有2种边——横着的和竖着的。横边在扫描线扫描过程中，应当在切换下一坐标之前消除。但是竖边应当用一个点来表示，考虑几何意义，应当在下一个横边之前消除。另外题目的特殊情况包括了r为0的点，要把他当做横边特殊判断一下。

#include<iostream>

#include <stdio.h>

#include<stdlib.h>

#include <assert.h>

#include <algorithm>

#include <cmath>

#include <set>

#include <vector>

using namespace std;

#define ll long long

#define ld long double

#define ppd pair<ld,ld>

#define equal(x,y) (abs(x-y)<=EXP)

#define idx(x) (lower_bound(mapp,mapp+mapp_num,x)-mapp)

#define init_coor(x) (equal(x.first,-2333666)&&equal(x.second,-2333666))

const int MAXN = ;

const ld EXP = 1e-;

const ld SQRT_2 = sqrt();

ppd rotate(ppd p){

    ld dis = sqrt(p.first*p.first+p.second*p.second);

    if(equal(dis,))return p;

    ld coss = (p.first - p.second)/(dis*SQRT_2);

    ld sins = (p.first + p.second)/(dis*SQRT_2);

    return make_pair(dis*coss,dis*sins);

}

ppd anti_rotate(ppd p){

    ld dis = sqrt(p.first*p.first+p.second*p.second);

    if(equal(dis,))return p;

    ld coss = (p.first + p.second)/(dis*SQRT_2);

    ld sins = (-p.first + p.second)/(dis*SQRT_2);

    return make_pair(dis*coss,dis*sins);

}

class Order{

    public:

        ld x1,x2,y;int key;

        int tt;

        Order(){}

        Order(ld x,ld xx,ld yy,int kk){

            this->x1 = x;

            this->x2 = xx;

            this->y = yy;

            this->key = kk;

            this->tt = ;

        }

};

inline bool is_negative_point(Order o){

    return(equal(o.x1,o.x2)&&o.key<&&o.tt);

}

inline bool is_positive_point(Order o){

    return(equal(o.x1,o.x2)&&o.key>&&o.tt);

}

inline bool is_point(Order o){

    return equal(o.x1,o.x2)&&o.tt;

}

bool cmp1(Order o1,Order o2){

    if(equal(o1.y,o2.y)){

        if(is_negative_point(o1) && !is_negative_point(o2))return true;

        if(!is_negative_point(o1) && is_negative_point(o2))return false;

        if(is_positive_point(o1) && !is_positive_point(o2))return false;

        if(!is_positive_point(o1) && is_positive_point(o2))return true;

        return o1.key > o2.key;

    }

    return o1.y<o2.y;

}

Order orders[MAXN];

int orders_num;

ld mapp[MAXN];

int mapp_num;

bool cmp(ld l1,ld l2){

    if(equal(l1,l2))return l1>l2;

    else return l1<l2;

}

void show(Order o){

    cout<<"check_order: "<<o.x1<<" "<<o.x2<<" at: "<<o.y<<" key: "<<o.key<<endl;

}

class Node{

    public:

        int l,r,lc,rc,num,lazy;

};

Node nodes[MAXN];

int nodes_num;

void tree_init(int a,int b){

    int now = nodes_num++;

    nodes[now].l = a;

    nodes[now].r = b;

    nodes[now].num = nodes[now].lazy = ;

    if(a == b-)return ;

    int mid = (a+b)/;

    nodes[now].lc = nodes_num;

    tree_init(a,mid);

    nodes[now].rc = nodes_num;

    tree_init(mid,b);

}

void push_down(int now){

    int lazy = nodes[now].lazy;

    nodes[now].lazy = ;

    int l = nodes[now].l;

    int r = nodes[now].r;

    if(l == r-)return ;

    int lc = nodes[now].lc;

    int rc = nodes[now].rc;

    nodes[lc].lazy += lazy;

    nodes[lc].num += lazy;

    nodes[rc].lazy += lazy;

    nodes[rc].num += lazy;

}

void tree_insert(int now,int a,int b,int key){

    int l = nodes[now].l;

    int r = nodes[now].r;

    push_down(now);

    if(a == l && b == r){

        nodes[now].num += key;

        nodes[now].lazy += key;

        return ;

    }

    int mid = (l+r)/;

    int lc = nodes[now].lc;

    int rc = nodes[now].rc;

    if(a<mid){

        tree_insert(lc,a,min(b,mid),key);

        if(b>mid) tree_insert(rc,mid,b,key);

    }else tree_insert(rc,a,b,key);

    nodes[now].num = max(nodes[nodes[now].lc].num,nodes[nodes[now].rc].num);

}

ld fitness_x,lasty;

void show(ppd p)

{

    // cout<<"check_coor: "<<p.first<<" "<<p.second<<endl;

    printf("check_coor: %.10lf %.10lf\n",(double)p.first,(double)p.second);

}

bool check_int(ppd p){

    p.first += EXP;

    p.second += EXP;

    // show(p);

    // printf("check_coor: %.5f %.5f %.5f %.5f\n",(double)p.first,(double)ceil(p.first),(double)p.second,(double)ceil(p.second));

    return equal(p.first,floor(p.first)) || equal(p.second,floor(p.second));

}

int find_max_num(int now){

    if(now == )fitness_x = -;

    int maxx = nodes[now].num;

    int l = nodes[now].l;

    int r = nodes[now].r;

    push_down(now);

    if(l == r-){

        ld xx = mapp[l];

        ld yy = lasty;

        ppd coor = make_pair(xx,yy);

        ppd std_coor = anti_rotate(coor);

        // show(coor);

        // show(std_coor);

        if(check_int(std_coor)){

            fitness_x = mapp[l];

            return ;

        }

        return ;

    }

    int lc = nodes[now].lc;

    int rc = nodes[now].rc;

    int ret = ;

    if(nodes[lc].num == maxx)ret += find_max_num(lc);

    if(nodes[rc].num == maxx)ret += find_max_num(rc);

    return ret;

}

int n;

ppd succ_coor;

void init(){

    nodes_num = ;

    orders_num = ;

    mapp_num = ;

    succ_coor = make_pair(-,-);

    mapp[mapp_num++] = 1e8;

    mapp[mapp_num++] = -1e8;

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

        ld x,y,r;

        cin>>x>>y>>r;

        ppd p1 = make_pair(x-r,y);

        ppd p2 = make_pair(x,y-r);

        ppd p3 = make_pair(x+r,y);

if(equal(r,)){

    ppd coor = rotate(make_pair(x,y));

    mapp[mapp_num++] = coor.first;

    orders[orders_num++] = Order(coor.first,coor.first,coor.second,);

    orders[orders_num-].tt = ;

    orders[orders_num++] = Order(coor.first,coor.first,coor.second,-);

    orders[orders_num-].tt = ;

    continue;

}

        // show(p1);

        // show(p2);

        // show(p3);

        p1 = rotate(p1);

        p2 = rotate(p2);

        p3 = rotate(p3);

        // show(anti_rotate(p1));

        // show(anti_rotate(p2));

        // show(anti_rotate(p3));

        orders[orders_num++] = Order(p1.first,p2.first,p1.second,);

        orders[orders_num++] = Order(p1.first,p2.first,p3.second,);

        orders[orders_num++] = Order(p1.first,p2.first,p1.second,-);

        orders[orders_num++] = Order(p1.first,p2.first,p3.second,-);

        orders[orders_num++] = Order(p1.first,p1.first,p1.second,);

        orders[orders_num++] = Order(p2.first,p2.first,p1.second,);

        orders[orders_num++] = Order(p1.first,p1.first,p3.second,-);

        orders[orders_num++] = Order(p2.first,p2.first,p3.second,-);

        mapp[mapp_num++] = p1.first;

        mapp[mapp_num++] = p2.first;

        // cout<<p1.first<<" "<<p2.first<<endl;

    }

    sort(orders,orders+orders_num,cmp1);

    sort(mapp,mapp+mapp_num,cmp);

    int len = mapp_num;

    mapp_num = ;

    for(int i=;i<len;++i){

                    // cout<<mapp[i]<<endl;

        if(!(equal(mapp[i],mapp[mapp_num]))){

            mapp_num++;

            mapp[mapp_num] = mapp[i];

        }

    }mapp_num++;

    tree_init(,mapp_num);

    int succ = ;

    lasty = orders[].y;

    for(int i=;i<orders_num;++i){

        // cout<<"circle: "<<i<<" "<<orders_num<<endl;

            // cout<<"check_num: "<<nodes[0].num<<endl;

            // show(orders[i]);

            // cout<<"check_mapp: "<<mapp[idx(orders[i].x1)]<<" "<<orders[i].x1<<endl;

            // printf("check_mapp: %.5f %.5f\n",(double)mapp[idx(orders[i].x1)],(double)orders[i].x1);

            // printf("check_mapp: %.5f %.5f\n",(double)mapp[idx(orders[i].x2)],(double)orders[i].x2);

        if(nodes[].num == n){

            int maxx_num = find_max_num();

            if(maxx_num >){

                succ = -;

                break;

            }

            if(maxx_num == )continue;

            if(init_coor(succ_coor))succ_coor = make_pair(fitness_x,lasty);

            else{

                succ = -;

                break;

            }

        }

        tree_insert(,idx(orders[i].x1),idx(orders[i].x2)+,orders[i].key);

        lasty = orders[i].y;

    }

    if(succ == -){

        puts("uncertain");

        return;

    }

    if(init_coor(succ_coor)){

        puts("impossible");

        return;

    }else{

        succ_coor = anti_rotate(succ_coor);

        // succ_coor.first += EXP;

        // succ_coor.second += EXP;

        printf("%.0f %.0f\n",(double)succ_coor.first,(double)succ_coor.second);

    }

}

int main(){

    while(cin>>n)init();

    return ;

}