結果

問題 No.325 マンハッタン距離2
ユーザー koyumeishi
提出日時 2015-12-18 13:47:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 5,740 bytes
コンパイル時間 965 ms
コンパイル使用メモリ 88,584 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 08:31:10
合計ジャッジ時間 1,812 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define EPS 1e-7
class xy{
public:
    long double x;
    long double y;
    xy() : x(0), y(0) {}
    xy(long double xx, long double yy) : x(xx), y(yy) {}
    xy(const xy& v) : x(v.x), y(v.y){}
    xy& operator = (const xy& v){
        x = v.x;
        y = v.y;
        return *this;
    }
    xy operator + (const xy& v) const{return xy(this->x+v.x, this->y+v.y);}
    xy operator - (const xy& v) const{return xy(this->x-v.x, this->y-v.y);}
    xy operator * (const long double& k) const{return xy(this->x * k, this->y * k);}
    
    void operator += (const xy& v){x+=v.x;  y+=v.y;}
    void operator -= (const xy& v){x-=v.x;  y-=v.y;}
    void operator *= (const long double& k){x*=k;  y*=k;}
    bool operator < (const xy& v) const{
        if(x!=v.x) return x < v.x;
        return y < v.y;
    }
    bool operator > (const xy& v) const{
        if(x!=v.x) return x > v.x;
        return y > v.y;
    }
    bool operator == (const xy& v) const{
        return fabs(x-v.x) + fabs(y-v.y) < EPS;
    }
};
xy operator * (const long double& k, const xy& v){return v*k;}
//u corss v
long double cross(const xy& u, const xy& v){
    return u.x*v.y - u.y*v.x;
}
//u dot v
long double dot(const xy& u, const xy& v){
    return u.x*v.x + u.y*v.y;
}
//distance between two points
long double dist_p_p(const xy& a, const xy& b){
    return sqrt( fabs(dot(a-b, a-b)) );
}
//distance between a point and a line segment
long double dist_p_ls(const xy &p, const xy &s1, const xy &s2){
    xy vl = s2 - s1;
    xy vp = p - s1;
    return fabs( cross(vl, vp) / sqrt( dot(vl, vl) ) );
}
int ccw(xy p1, xy p2, xy p3){
    p2 -= p1;
    p3 -= p1;
    long double c = cross(p2,p3);
    if( c > EPS /* c > 0 */) return +1;             //counter-clockwise
    if( c < -EPS /* c < 0 */) return -1;            //clock-wise
    if( dot(p2,p3) < -EPS) return +2;               //out of segment : p3-p1-p2
    if( dot(p3,p3) - dot(p2,p2) > EPS) return -2;   //out of segment : p1-p2-p3
    return 0;                                       //on the segment : p1-p3-p2
}
//are two segment p1-p2 , p3-p4 parallel?
bool is_parallel(xy p1, xy p2, xy p3, xy p4){
    return abs(ccw(p1,p2, p3))!=1 && abs(ccw(p1,p2, p4))!=1;
}
//intersect
//segment p1-p2, p3-p4
bool inter_ss(xy p1, xy p2, xy p3, xy p4){
    int ret1 = ccw(p1,p2, p3) * ccw(p1,p2, p4);
    int ret2 = ccw(p3,p4, p1) * ccw(p3,p4, p2);
    return ret1 <= 0 && ret2 <= 0;
}
bool inter_ss(const pair<xy,xy>& l1, const pair<xy,xy>& l2){
    return inter_ss(l1.first, l1.second, l2.first, l2.second);
}
//return crossing point l1 and l2 without checking
xy inter_point(const pair<xy,xy>& l1, const pair<xy,xy>& l2){
    long double a = cross(l2.second - l1.first, l2.second - l2.first);
    //long double b = cross(l1.second - l1.first, l2.second - l1.first);
    long double c = cross(l1.second - l1.first, l2.second - l2.first);
    long double lam = a/c;
    return l1.first + (l1.second - l1.first)*lam;
}
//convex_hull
//O(n log n)
vector<xy> convex_hull(vector<xy> &v){
    if(v.size() == 0){
        return {};
    }
    sort( v.begin(), v.end() );
    int k = 0;  //nums of vertex
    vector<xy> tmp(v.size()*2);
    //conect i from k
    for(int i=0; i<v.size(); i++){
        while(k>1 && cross (tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
        tmp[k] = v[i];
        k++;
    }
    
    for(int i=v.size()-2, t=k; i>=0; i--){
        while(k>t && cross(tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
        tmp[k] = v[i];
        k++;
    }
    tmp.resize(k-1);
    return tmp;
}
//O(n)
long double polygon_area(const vector<xy>& poly){
    long double ret = 0;
    for(int i=0; i<poly.size(); i++){
        ret += cross(poly[i], poly[(i+1)%poly.size()]);
    }
    return ret*0.5;
}
//O(n)
bool point_inner_polygon(const xy& p, const vector<xy>& poly){
    bool ret = false;
    for(int i=0; i<poly.size(); i++){
        xy high = poly[i] - p;
        xy low = poly[(i+1)%poly.size()] - p;
        if(high.y<low.y) swap(high, low);
        if(high.y>=0 && low.y < 0){
            if(cross(low,high) > 0) ret = !ret;
        }
        if(fabs(cross(low,high)) < EPS && dot(high,low)<EPS){
            return true; //on the segment
        }
    }
    return ret;
}
ostream& operator << (ostream& os, xy& p){
    os << "{" << p.x << ", " << p.y << "}";
    return os;
}
template<class T>
ostream& operator << (ostream& os, vector<T> vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << " ";
    }
    return os;
}
template<class T> istream& operator , (istream& is, T& val){is >> val; return is;}
#include <cassert>
int main(){
    long long x1,y1,x2,y2, d;
    cin >> x1,y1,x2,y2,d;
    vector<xy> rho = {xy(0,d), xy(d,0), xy(0,-d), xy(-d,0)};
    vector<xy> rec = {xy(x1,y1), xy(x1,y2), xy(x2,y2), xy(x2,y1)};
    if(d==0){
        cout << (point_inner_polygon(xy(0,0), rec)?1:0) << endl;
        return 0;
    }
    vector<xy> p;
    for(int i=0; i<rho.size(); i++){
        for(int j=0; j<rec.size(); j++){
            if(inter_ss(rho[i],rho[(i+1)%rho.size()], rec[j], rec[(j+1)%rec.size()])){
                if(is_parallel(rho[i],rho[(i+1)%rho.size()], rec[j], rec[(j+1)%rec.size()]) == false){
                    p.push_back( inter_point({rho[i],rho[(i+1)%rho.size()]}, {rec[j], rec[(j+1)%rec.size()]}) );
                }
            }
        }
    }
    for(int j=0; j<rec.size(); j++){
        if(point_inner_polygon(rec[j], rho)){
            p.push_back(rec[j]);
        }
    }
    for(int i=0; i<rho.size(); i++){
        if(point_inner_polygon(rho[i], rec)){
            p.push_back(rho[i]);
        }
    }
    sort(p.begin(), p.end());
    p.erase( unique(p.begin(), p.end()), p.end());
    //cerr << p << endl;
    if(p.size()<=1){
        cout << p.size() << endl;
        return 0;
    }
    vector<xy> hull = convex_hull(p);
    long double s = polygon_area(hull);
    long long lattice_b = 0;
    for(int i=0; i<hull.size(); i++){
        xy tmp = hull[i]-hull[(i+1)%hull.size()];
        lattice_b += max(fabs(tmp.x), fabs(tmp.y)) + EPS;
    }
    long long lattice_i = (s - lattice_b/2 + 1) + EPS;
    long long ans = lattice_b + lattice_i;
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0