結果
問題 | No.325 マンハッタン距離2 |
ユーザー | koyumeishi |
提出日時 | 2015-12-18 14:07:01 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 5,675 bytes |
コンパイル時間 | 947 ms |
コンパイル使用メモリ | 88,800 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-16 08:31:40 |
合計ジャッジ時間 | 1,808 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
ソースコード
#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 typedef long double Double; class xy{ public: Double x; Double y; xy() : x(0), y(0) {} xy(Double xx, 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 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 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 Double& k, const xy& v){return v*k;} //u corss v Double cross(const xy& u, const xy& v){ return u.x*v.y - u.y*v.x; } //u dot v Double dot(const xy& u, const xy& v){ return u.x*v.x + u.y*v.y; } //distance between two points 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 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; 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){ Double a = cross(l2.second - l1.first, l2.second - l2.first); //Double b = cross(l1.second - l1.first, l2.second - l1.first); Double c = cross(l1.second - l1.first, l2.second - l2.first); 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) Double polygon_area(const vector<xy>& poly){ 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); 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*0.5 + 1) + EPS; long long ans = lattice_b + lattice_i; cout << ans << endl; return 0; }