srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

aoj 1318 Long Distance Taxi

問題

問題概要

グラフがあたえられる. 各頂点のいくつかはガソリンステーションでガソリンを入れることができる. ガソリンがなくならずに, スタートからゴールに行くまでの最短距離を求める.
またLPGのタンクの最大容量もあたえられる. 車の燃費は10km/Lである.

解法

dist[i][j] := 頂点iまで残りLPGがjで来た時の最短距離
という状態を拡張ダイクストラで計算していく.
気をつけなければならないところは, 与えられたcapと燃費10km/Lのままだと, 道の距離が1kmの時, タンクから0.1を引かなければならなくなり, 少数がでてしまう.
だから, capを10倍することでこれを回避できる.

ミス

ガソスタがあるときは, そこでガソリンを満タンにしてしまえばいい.
満タン以外にもすこしいれるなどの処理をしてしまったらTLEした. (下のコード参照)

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

map<string, int> city2num;
set<int> LPG;

vector<pair<int, int>> G[6010];
int dist[6010][2010]; // dist[i][j] := 頂点iまで残りLPGがjで来た時の最短距離
using tup = tuple<int, int, int>;

void dijkstra(int start, int cap){
    rep(i, 6010)rep(j, 2010) dist[i][j] = INF;
    cap *= 10;
    dist[start][cap] = 0;
    priority_queue<tup, vector<tup>, greater<tup> >  que; // 距離 頂点 残りのLPG
    que.push(make_tuple(0, start, cap));
    while(!que.empty()){
        int cost, u, lpg;
        tie(cost, u, lpg) = que.top(); que.pop();
        if(dist[u][lpg] < cost) continue;
        for (auto& tmp : G[u]){
            int v = tmp.first, di = tmp.second;
            int nlpg = lpg - di;
            int ncost = cost + di;
            if(nlpg < 0) continue;
            if(LPG.count(v)) {
                /*
                for (int i = nlpg; i <= cap; ++i){ これだとTLE(9.0s)
                    if(dist[v][i] > ncost) {
                        dist[v][i] = ncost;
                        que.push(make_tuple(ncost, v, i));
                    }
                }
                */
                if(dist[v][cap] > ncost) {
                    dist[v][cap] = ncost;
                    que.push(make_tuple(ncost, v, cap));
                }
            }else{
                if(dist[v][nlpg] > ncost) {
                    dist[v][nlpg] = ncost;
                    que.push(make_tuple(ncost, v, nlpg));
                }
            }
        }
    }
}


string c1[6010], c2[6010];
int d[6010];
string s[6010];
int main(void) {
    while(1){
        city2num.clear(); LPG.clear();
        rep(i, 6010) G[i].clear();

        int N, M, cap; scanf("%d %d %d", &N, &M, &cap);
        if(N == 0 && M == 0 && cap == 0) break;
        string src, dest; cin >> src >> dest;

        rep(i, N) cin >> c1[i] >> c2[i] >> d[i];
        rep(i, M) cin >> s[i];

        set<string> city;
        rep(i, N) city.insert(c1[i]), city.insert(c2[i]);
        int cnt = 0;
        for(auto& u : city) {
            city2num[u] = cnt++;
        }
        rep(i, M) LPG.insert(city2num[s[i]]);

        rep(i, N) G[city2num[c1[i]]].pb(mp(city2num[c2[i]], d[i])), G[city2num[c2[i]]].pb(mp(city2num[c1[i]], d[i]));
        int ns = city2num[src], nd = city2num[dest];

        dijkstra(ns, cap);
        ll ans = INF;
        rep(i, cap * 10 + 1) chmin(ans, dist[nd][i]);
        if(ans != INF)printf("%lld\n", ans);
        else printf("-1\n");
    }
    return 0;
}

九州大学プログラミングコンテスト2014 H - お風呂は気持ちいい

問題

問題概要

頂点の間の容量が与えられる. 複数のスタートから一つのゴールまで最大どのくらいのものを運ぶことができるか.

解法

G個のスタート地点があるので, スタート地点の頂点を新たに作り, そこから魔導石に近い魔法使いへ辺の容量がINFの辺をはる. あとは与えられた辺をそのままはって, スタート地点からアスナにどれだけ流せるかをフローで求めれば良い.

ミス

最大流の基本的な問題.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

const int MAX_V = 510; //必要な頂点数
struct Flow{
    struct edge{
        int to, cap, rev;
    };
    vector<edge> G[MAX_V];//隣接リスト
    bool used[MAX_V];
 
    void add_edge(int from, int to, int cap){
        G[from].push_back((edge){to, cap, (int)G[to].size()});//from -> to
        G[to].push_back((edge){from, 0, (int)G[from].size() - 1});//to -> from
    }
    //増加パスを探す
    int dfs(int v, int t, int f){
        if(v == t) return f;
        used[v] = true;
        for (int i = 0; i < G[v].size(); ++i){
            edge &e = G[v][i];
            if(!used[e.to] && e.cap > 0){
                int d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    //sからtへの最大流
    int max_flow(int s, int t){
        int flow = 0;
        while(1){
            memset(used, 0, sizeof(used));
            int f = dfs(s, t, INF);
            if(f == 0) return flow;
            flow += f;
        }
    }
};


int N, M, P, G;
int L[12];
int from[510], to[510], cap[510];

int main(void) {
    cin >> N >> M >> P >> G;
    rep(i, G) cin >> L[i];
    rep(i, N) cin >> from[i] >> to[i] >> cap[i];
    Flow f;
    int start = N + 1;
    rep(i, G) f.add_edge(start, L[i], INF);
    rep(i, N) f.add_edge(from[i], to[i], cap[i]);
    int ret = f.max_flow(start, 0);
    if(ret < P) printf("No\n");
    else printf("Yes\n");
    return 0;
}

aoj 2402 Milky Way

問題

問題概要

五芒星が与えられる. スタートの星からゴールの星までの移動の最小距離を求める. 星の中は移動距離に入らない.

解法

星と星の距離は, 各星は5つの辺からなっていることから, 5つの辺ぞれぞれを総当りで調べて, その中の最小値が距離になる. このように距離を求めて, ダイクストラを行えば良い.

ミス

点を回転させる部分を間違えてて, 辛かった.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> bool eq(T a, T b){ return abs(a - b) < EPS; }

class Point { // 点
public:
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){}
    Point operator + (Point p) { return Point(x + p.x, y + p.y); }
    Point operator - (Point p) { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(a * x, a * y); }
    Point operator / (double a) { return Point(x / a, y / a); }
    double abs() const { return sqrt(norm()); }
    double norm() const { return x * x + y * y; }
    // bool operator < (const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
    bool operator < (const Point &p) const { // 誤差を許容して比較
        return x + EPS < p.x || (eq<double>(x, p.x) && y + EPS < p.y);
    }
    bool operator == (const Point &p) const { return (eq<double>(x, p.x) && eq<double>(y, p.y)); }
};
using Vector = Point;
using Polygon = vector<Point>; // 多角形

double dot(const Vector& a, const Vector& b) { return a.x * b.x + a.y * b.y; } // ベクトルaとbの内積
double cross(const Vector& a, const Vector& b) { return a.x * b.y - a.y * b.x; } // ベクトルaとbの外積
double length2(const Point& a) { return a.norm(); } // 通常の長さの2乗
double length(const Point& a) { return a.abs(); } // 通常の長さ
Point rotationalTransfer(Point c, double r, double deg) { // cを中心として半径rの円周上のdeg度の位置座標
    double rad = PI * deg / 180.0; return c + Point(cos(rad), sin(rad)) * r;
}

enum ccw_t {
    COUNTER_CLOCKWISE = 1, // p0->p1 反時計回りの方向にp2
    CLOCKWISE = -1, // p0->p1 時計回りの方向にp2
    ONLINE_BACK = 2, // p2->p0->p1 の順で直線上でp2
    ONLINE_FRONT = -2, // p0->p1->p2 の順で直線上p2
    ON_SEGMENT = 0, // p0->p2->p1 の順で線分p0p1上にp2
};
ccw_t ccw(Point p0, Point p1, Point p2) {
    Vector a = p1 - p0, b = p2 - p0;
    if ( cross(a, b) > EPS  )  return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS )  return CLOCKWISE;
    if ( dot(a, b) < -EPS )    return ONLINE_BACK;
    if ( a.norm() < b.norm() ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

class Segment { //線分
public:
    Point p1, p2;
    Segment(){}
    Segment(Point p1, Point p2):p1(p1), p2(p2){}
};
using Line = Segment;

// *** 線分の交差判定 ***
bool intersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
    return ( ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && 
             ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}
bool intersect(const Segment& s1, const Segment& s2) { // 交差していたらtrue
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}
//*** 線分の交点 ***
Point getCrossPoint(Segment s1, Segment s2) { // 線分の交点が存在するから調べた後つかうこと
    Vector base = s2.p2 - s2.p1;
    double d1 = abs(cross(base, s1.p1 - s2.p1)), d2 = abs(cross(base, s1.p2 - s2.p1));
    double t  = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
}
// *** 距離 ***
double getDistance(Point& a, Point& b) { // 点aと点bの距離
    return length(a - b);
}
double getDistanceLP(Line& l, Point& p) { // 直線sと点pの距離
    return length(cross(l.p2 - l.p1, p - l.p1) / length(l.p2 - l.p1));
}
double getDistanceSP(Segment s, Point p) { // 線分sと点pの距離
    if( dot(s.p2 - s.p1, p - s.p1) < EPS ) return length(p - s.p1);
    if( dot(s.p1 - s.p2, p - s.p2) < EPS ) return length(p - s.p2);
    return getDistanceLP(s, p);
}
double getDistanceSS(Segment s1, Segment s2) { // 線分s1と線分s2の交点
    if( intersect(s1, s2) ) return 0.0; //交わっているとき
    return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
               min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
}

class Rectangle { // 長方形
public:
    // 3 2
    // 0 1 (反時計回りに長方形の頂点をいれること)
    vector<Point> p; // 点を順番にいれること
    Rectangle(vector<Point>&p):p(p) {
        rep(i, 3) reps(j, i + 1, 4) { //適当な順番にいれても大丈夫なように?
            int cnt = 0;
            rep(k, 4) if(k != i && k != j) {
                cnt += ccw(p[i], p[j], p[k]) == COUNTER_CLOCKWISE;
            }
            if(cnt == 2) {
                swap(p[i + 1], p[j]);
                break;
            }
        }
    }
    bool intersect(const Segment& s) { // 線分sと長方形の少なくとも1辺が交差していればtrue
        bool flag = false;
        rep(i, 4) flag |= ::intersect(s, Segment(p[i], p[(i + 1) % 4]));
        return flag;
    }
    bool contain(const Point& pp) { // 点ppが長方形内に含まれれば(辺を含まない)true
        bool flag = true;
        rep(i, 4) flag &= ccw(p[i], p[(i + 1) % 4], pp) == COUNTER_CLOCKWISE;
        return flag;
    }
    bool contain(const Segment& s) { // 線分sが長方形内に含まれれば(辺を含まない)true
        return contain(s.p1) && contain(s.p2);
    }
};

const int MAX_N = 210;
using TYPE = double; // 距離の型を入れる
vector<pair<int, TYPE> > G[MAX_N];
vector<TYPE> dijkstra(int start){
    vector<TYPE> dist(MAX_N, INFF);
    dist[start] = 0;//dist[i] := start->iまでの最短距離
    priority_queue<pair<TYPE, int>, vector<pair<TYPE, int> >, greater<pair<TYPE, int> > >  que;
    que.push(make_pair(0, start));
    while(!que.empty()){
        TYPE cost; int u;//今までにかかった時間 現在の頂点
        cost = que.top().first, u = que.top().second;
        que.pop();
        if(dist[u] < cost) continue;
        for (auto tmp : G[u]){
            int v = tmp.first; TYPE time = tmp.second;//隣接する頂点 その頂点まで行く時間
            if(dist[v] > dist[u] + time){//u->v
                dist[v] = dist[u] + time;
                que.push(make_pair(dist[v], v));
            }
        }
    }
    return dist;
}


int main(void){
    
    while(1) {

        int N, M, L; scanf("%d %d %d", &N, &M, &L);
        if(N == 0 && M == 0 && L == 0) break;
        M--, L--;
        vector<vector<Segment>> star;
        
        rep(i, N){
            double x, y, a, r; scanf("%lf %lf %lf %lf", &x, &y, &a, &r);
            Point c(x, y);
            vector<Point> v;

            rep(j, 5) {
                // double rad = (90 + a + j * 72) * PI / 180.0;
                // v.pb(Point(x, y) + Point(cos(rad), sin(rad)) * r);
                v.pb(rotationalTransfer(c, r, 90 + a + j * 72.));
            }
            
            
            vector<Segment> seg;
            // 星の5辺を追加
            rep(j, 5) seg.pb(Segment(v[j % 5], v[(j + 2) % 5]));
            star.pb(seg);
        }
        
        rep(i, MAX_N) G[i].clear();

        rep(i, star.size())rep(j, star.size()){
            if(i == j) continue;
            double mi = INF;
            for(auto u : star[i])for(auto v : star[j]){
                chmin(mi, getDistanceSS(u, v));
            }
            // printf("mi %f\n", mi);
            G[i].pb(mp(j, mi)), G[j].pb(mp(i, mi));
        }

        auto ret = dijkstra(M);
        printf("%.9f\n", ret[L]);

    }
    
    return 0;
}

aoj 1157 Roll-A-Big-Ball

問題

問題概要

ボールが通る線分とそれをじゃまするN個の直方体が与えられる.
直方体に重ならずに線分をスタートからゴールまで通ることができるボールの半径の最大値を求める.

解法

長方形と線分の距離をdとして求める半径をrとすると,
d <= hのとき, r = d
d > hのとき, (d * d + h * h) / (2 * h) (三平方の定理)
と求めることができるので, これをすべての長方形に対して行い, rの最小値を答えとすればいい.
ただし, 線分と長方形が交わっている場合, 答えは0になるので, そのチェックをすること.

ミス

線分と長方形の頂点との距離のみを考えていて,WAした.
線分と長方形の4辺の距離を考えないとだめ. 長方形の頂点が線分と一番近い点とは限らない.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = max(a, b);
#define chmin(a, b) a = min(a, b);
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;



const double EPS = 1e-10;
template<class T> bool eq(T a, T b){ return abs(a - b) < EPS; }

class Point { // 点
public:
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){}
    Point operator + (Point p) { return Point(x + p.x, y + p.y); }
    Point operator - (Point p) { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(a * x, a * y); }
    Point operator / (double a) { return Point(x / a, y / a); }
    double abs() const { return sqrt(norm()); }
    double norm() const { return x * x + y * y; }
    // bool operator < (const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
    bool operator < (const Point &p) const { // 誤差を許容して比較
        return x + EPS < p.x || (eq<double>(x, p.x) && y + EPS < p.y);
    }
    bool operator == (const Point &p) const { return (eq<double>(x, p.x) && eq<double>(y, p.y)); }
};
using Vector = Point;

double dot(const Vector& a, const Vector& b) { return a.x * b.x + a.y * b.y; } // ベクトルaとbの内積
double cross(const Vector& a, const Vector& b) { return a.x * b.y - a.y * b.x; } // ベクトルaとbの外積
double length2(const Point& a) { return a.norm(); } // 通常の長さの2乗
double length(const Point& a) { return a.abs(); } // 通常の長さ

enum ccw_t {
    COUNTER_CLOCKWISE = 1, // p0->p1 反時計回りの方向にp2
    CLOCKWISE = -1, // p0->p1 時計回りの方向にp2
    ONLINE_BACK = 2, // p2->p0->p1 の順で直線上でp2
    ONLINE_FRONT = -2, // p0->p1->p2 の順で直線上p2
    ON_SEGMENT = 0, // p0->p2->p1 の順で線分p0p1上にp2
};
ccw_t ccw(Point p0, Point p1, Point p2) {
    Vector a = p1 - p0, b = p2 - p0;
    if ( cross(a, b) > EPS  )  return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS )  return CLOCKWISE;
    if ( dot(a, b) < -EPS )    return ONLINE_BACK;
    if ( a.norm() < b.norm() ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

class Segment { //線分
public:
    Point p1, p2;
    Segment(){}
    Segment(Point p1, Point p2):p1(p1), p2(p2){}
};
using Line = Segment;

// *** 線分の交差判定 ***
bool intersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
    return ( ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && 
             ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}
bool intersect(const Segment& s1, const Segment& s2) { // 交差していたらtrue
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}
//*** 線分の交点 ***
Point getCrossPoint(Segment s1, Segment s2) {
    Vector base = s2.p2 - s2.p1;
    double d1 = abs(cross(base, s1.p1 - s2.p1)), d2 = abs(cross(base, s1.p2 - s2.p1));
    double t  = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
}
// *** 距離 ***
double getDistance(Point& a, Point& b) { // 点aと点bの距離
    return length(a - b);
}
double getDistanceLP(Line& l, Point& p) { // 直線sと点pの距離
    return length(cross(l.p2 - l.p1, p - l.p1) / length(l.p2 - l.p1));
}
double getDistanceSP(Segment s, Point p) { // 線分sと点pの距離
    if( dot(s.p2 - s.p1, p - s.p1) < EPS ) return length(p - s.p1);
    if( dot(s.p1 - s.p2, p - s.p2) < EPS ) return length(p - s.p2);
    return getDistanceLP(s, p);
}
double getDistanceSS(Segment s1, Segment s2) {
    if( intersect(s1, s2) ) return 0.0;
    return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
               min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
}

class Rectangle { // 長方形
public:
    // 3 2
    // 0 1 (反時計回りに長方形の頂点をいれること)
    vector<Point> p; // 点を順番にいれること
    Rectangle(vector<Point>&p):p(p) {
        rep(i, 3) reps(j, i + 1, 4) { //適当な順番にいれても大丈夫なように?
            int cnt = 0;
            rep(k, 4) if(k != i && k != j) {
                cnt += ccw(p[i], p[j], p[k]) == COUNTER_CLOCKWISE;
            }
            if(cnt == 2) {
                swap(p[i + 1], p[j]);
                break;
            }
        }
    }
    bool intersect(const Segment& s) { // 線分sと長方形の少なくとも1辺が交差していればtrue
        bool flag = false;
        rep(i, 4) flag |= ::intersect(s, Segment(p[i], p[(i + 1) % 4]));
        return flag;
    }
    bool contain(const Point& pp) { // 点ppが長方形内に含まれれば(辺を含まない)true
        bool flag = true;
        rep(i, 4) flag &= ccw(p[i], p[(i + 1) % 4], pp) == COUNTER_CLOCKWISE;
        return flag;
    }
    bool contain(const Segment& s) { // 線分sが長方形内に含まれれば(辺を含まない)true
        return contain(s.p1) && contain(s.p2);
    }
};



int main(void) {
    
    while(1) {
        int N; scanf("%d", &N);
        if(N == 0) break;
        double sx, sy, ex, ey; scanf("%lf %lf %lf %lf", &sx, &sy, &ex, &ey);
        double minx[55], miny[55], maxx[55], maxy[55], h[55];
        rep(i, N) scanf("%lf %lf %lf %lf %lf", &minx[i], &miny[i], &maxx[i], &maxy[i], &h[i]);

        Segment L(Point(sx, sy), Point(ex, ey));

        double ans = INF;
        rep(i, N) {
            vector<Point> tmp({Point(minx[i], miny[i]), Point(maxx[i], miny[i]), Point(maxx[i], maxy[i]), Point(minx[i], maxy[i])});
            Rectangle rec(tmp);
            if(rec.intersect(L) || rec.contain(L)) {
                ans = 0.0;
                continue;
            }
            
            double d = INF;
            chmin(d, getDistanceSS(L, Segment(Point(minx[i], miny[i]), Point(minx[i], maxy[i]))));
            chmin(d, getDistanceSS(L, Segment(Point(minx[i], maxy[i]), Point(maxx[i], maxy[i]))));
            chmin(d, getDistanceSS(L, Segment(Point(maxx[i], maxy[i]), Point(maxx[i], miny[i]))));
            chmin(d, getDistanceSS(L, Segment(Point(maxx[i], miny[i]), Point(minx[i], miny[i]))));

            double r;
            if(d <= h[i]) r = d;
            else r = (d * d + h[i] * h[i]) / (2 * h[i]);

            chmin(ans, r);
        }
        printf("%.9f\n", ans);
    }
    
    return 0;
}

aoj 2009 Area Separation

問題

問題概要

頂点を(-100,-100)、(100,-100)、(100,100)、(-100,100) とする正方形とn個の線分が与えられる. 線分の両端は正方形の辺上にある. 線分により正方形がいくつに分割されるかを求めよ.

解法

順番に線分を書いていくことを考える. いま書く線分とすでに書かれているすべての線分との交点の集合の要素の数を求めると, いま書く線分によって新たに作られる領域の数は, 交点の数 + 1 となる.
ただし, 正方形の辺上にできる線分どうしの交点は交点に含まない.
Point型には比較関数 < を定義しているので, もとめた交点をsetにいれていけば, 重複をゆるさず交点の数をカウントすることができる.

ミス

Point型に定義している operator < をどうするべきなのかわからない.

const double EPS = 1e-10;
template<class T> bool eq(T a, T b){ return abs(a - b) < EPS; }

class Point { // 点
public:
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){}
    Point operator + (Point p) { return Point(x + p.x, y + p.y); }
    Point operator - (Point p) { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(a * x, a * y); }
    Point operator / (double a) { return Point(x / a, y / a); }
    double abs() const { return sqrt(norm()); }
    double norm() const { return x * x + y * y; }
    bool operator < (const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
    bool operator == (const Point &p) const { return (eq<double>(x, p.x) && eq<double>(y, p.y)); }
};

int main(void) {
    set<Point> se1;
    se1.insert({
        Point(1.000000000001, 1.000000000001),
        Point(1.000000000002, 1.000000000002),
        Point(1.000000000003, 1.000000000003),
        Point(1.000000000004, 1.000000000004),
        Point(1.000000000005, 1.000000000005),
        Point(1.000000000001, 1.000000000005),
        Point(1.000000000002, 1.000000000004),
    });
    cout << se1.size() << endl;
    return 0;
}

上のコードの出力は7となってしまう.

const double EPS = 1e-10;
template<class T> bool eq(T a, T b){ return abs(a - b) < EPS; }

class Point { // 点
public:
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){}
    Point operator + (Point p) { return Point(x + p.x, y + p.y); }
    Point operator - (Point p) { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(a * x, a * y); }
    Point operator / (double a) { return Point(x / a, y / a); }
    double abs() const { return sqrt(norm()); }
    double norm() const { return x * x + y * y; }
    bool operator < (const Point &p) const { // 誤差を許容して比較
        return x + EPS < p.x || (eq<double>(x, p.x) && y + EPS < p.y);
    }
    bool operator == (const Point &p) const { return (eq<double>(x, p.x) && eq<double>(y, p.y)); }
};

int main(void) {
    set<Point> se1;
    se1.insert({
        Point(1.000000000001, 1.000000000001),
        Point(1.000000000002, 1.000000000002),
        Point(1.000000000003, 1.000000000003),
        Point(1.000000000004, 1.000000000004),
        Point(1.000000000005, 1.000000000005),
        Point(1.000000000001, 1.000000000005),
        Point(1.000000000002, 1.000000000004),
    });
    cout << se1.size() << endl;
    return 0;
}

上のコードの出力は1となる.
今回の問題では, どちらのoperator < でもACできたが, 上のコードでは誤差を考えた比較関数になっていないので, ケースによってはだめかもしれない?
operator < はどうすべきなんだ?

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = max(a, b);
#define chmin(a, b) a = min(a, b);
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


const double EPS = 1e-10;
template<class T> bool eq(T a, T b){ return abs(a - b) < EPS; }

class Point { // 点
public:
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){}
    Point operator + (Point p) { return Point(x + p.x, y + p.y); }
    Point operator - (Point p) { return Point(x - p.x, y - p.y); }
    Point operator * (double a) { return Point(a * x, a * y); }
    Point operator / (double a) { return Point(x / a, y / a); }
    double abs() const { return sqrt(norm()); }
    double norm() const { return x * x + y * y; }
    // bool operator < (const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
    bool operator < (const Point &p) const { // 誤差を許容して比較
        return x + EPS < p.x || (eq<double>(x, p.x) && y + EPS < p.y);
    }
    bool operator == (const Point &p) const { return (eq<double>(x, p.x) && eq<double>(y, p.y)); }
};
using Vector = Point;

double dot(const Vector& a, const Vector& b) { return a.x * b.x + a.y * b.y; } // ベクトルaとbの内積
double cross(const Vector& a, const Vector& b) { return a.x * b.y - a.y * b.x; } // ベクトルaとbの外積
double length2(const Point& a) { return a.norm(); } // 通常の長さの2乗
double length(const Point& a) { return a.abs(); } // 通常の長さ

enum ccw_t {
    COUNTER_CLOCKWISE = 1, // p0->p1 反時計回りの方向にp2
    CLOCKWISE = -1, // p0->p1 時計回りの方向にp2
    ONLINE_BACK = 2, // p2->p0->p1 の順で直線上でp2
    ONLINE_FRONT = -2, // p0->p1->p2 の順で直線上p2
    ON_SEGMENT = 0, // p0->p2->p1 の順で線分p0p1上にp2
};
ccw_t ccw(Point p0, Point p1, Point p2) {
    Vector a = p1 - p0, b = p2 - p0;
    if ( cross(a, b) > EPS  )  return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS )  return CLOCKWISE;
    if ( dot(a, b) < -EPS )    return ONLINE_BACK;
    if ( a.norm() < b.norm() ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

class Segment { //線分
public:
    Point p1, p2;
    Segment(){}
    Segment(Point p1, Point p2):p1(p1), p2(p2){}
};
using Line = Segment;

// *** 線分の交差判定 ***
bool intersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
    return ( ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && 
             ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}
bool intersect(const Segment& s1, const Segment& s2) { // 交差していたらtrue
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}
//*** 線分の交点 ***
Point getCrossPoint(Segment s1, Segment s2) {
    Vector base = s2.p2 - s2.p1;
    double d1 = abs(cross(base, s1.p1 - s2.p1)), d2 = abs(cross(base, s1.p2 - s2.p1));
    double t  = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
}
// *** 距離 ***
double getDistance(Point& a, Point& b) { // 点aと点bの距離
    return length(a - b);
}
double getDistanceLP(Line& l, Point& p) { // 直線sと点pの距離
    return length(cross(l.p2 - l.p1, p - l.p1) / length(l.p2 - l.p1));
}
double getDistanceSP(Segment s, Point p) { // 線分sと点pの距離
    if( dot(s.p2 - s.p1, p - s.p1) < EPS ) return length(p - s.p1);
    if( dot(s.p1 - s.p2, p - s.p2) < EPS ) return length(p - s.p2);
    return getDistanceLP(s, p);
}
double getDistanceSS(Segment s1, Segment s2) {
    if( intersect(s1, s2) ) return 0.0;
    return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
               min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
}

class Rectangle { // 長方形
public:
    // 3 2
    // 0 1 (反時計回りに長方形の頂点をいれること)
    vector<Point> p; // 点を順番にいれること
    Rectangle(vector<Point>&p):p(p) {
        rep(i, 3) reps(j, i + 1, 4) { //適当な順番にいれても大丈夫なように?
            int cnt = 0;
            rep(k, 4) if(k != i && k != j) {
                cnt += ccw(p[i], p[j], p[k]) == COUNTER_CLOCKWISE;
            }
            if(cnt == 2) {
                swap(p[i + 1], p[j]);
                break;
            }
        }
    }
    bool intersect(const Segment& s) { // 線分sと長方形の少なくとも1辺が交差していればtrue
        bool flag = false;
        rep(i, 4) flag |= ::intersect(s, Segment(p[i], p[(i + 1) % 4]));
        return flag;
    }
    bool contain(const Point& pp) { // 点ppが長方形内に含まれれば(辺を含まない)true
        bool flag = true;
        rep(i, 4) flag &= ccw(p[i], p[(i + 1) % 4], pp) == COUNTER_CLOCKWISE;
        return flag;
    }
    bool contain(const Segment& s) { // 線分sが長方形内に含まれれば(辺を含まない)true
        return contain(s.p1) && contain(s.p2);
    }
};


int main(void) {

    while(1) {

        int n; scanf("%d", &n);
        if(n == 0) break;
        double x1[110], y1[110], x2[110], y2[110];
        rep(i, n) scanf("%lf %lf %lf %lf", &x1[i], &y1[i], &x2[i], &y2[i]);

        if(n == 1){
            printf("2\n"); break;
        }
        int ans = 2;
        reps(i, 1, n){
            set<Point> se;
            rep(j, i){
                Segment u(Point(x1[i], y1[i]), Point(x2[i], y2[i])), 
                        v(Point(x1[j], y1[j]), Point(x2[j], y2[j]));
                if(!intersect(u, v)) continue;
                se.insert(getCrossPoint(u, v));
            }

            // 長方形の円周上の点を除く
            for(auto t : se) {
                if(eq<double>(t.x, -100.0) || eq<double>(t.x, 100.0) || 
                   eq<double>(t.y, -100.0) || eq<double>(t.y, 100.0)){
                    se.erase(t);
                }
            }

            ans += (int)se.size() + 1;
        }
        printf("%d\n", ans);

    }
    return 0;
}

aoj 1176 Planning Rolling Blackouts

問題

問題概要

長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける.
分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合計値)が供給量を超えてはならない. さらに分割数を最大にし, さらに予備力(供給力と最大抑制需要の差)を最大にしなければならない.

解法

まず長方形の角を指定したら, その中のマスの値の合計値がO(1)で求まるように, 二次元累積和用いて計算できるようにしておく.
あとは, dp[y1][x1][y2][x2] := 左上(y1, x1), 右下(y2, x2)の長方形を考えた時の, グループの分け方の最大数と最大の予備力
という状態を考えてdpしていく.
ある長方形を考えた時に, 分割する方法は縦にどこかで切るか, 横にどこかで切るか(またはこれ以上きれない)しかないのでこれらをすべて試せば良い. これをdfsの中で行っている. 値の更新方法は長方形を切り, 作られた2つの長方形それぞれのグループの分け方と予備力の最大値を用いて, 更新することができる. グループの分け方は2つの長方形の値を単に足せばよくて, 予備力は供給力と最大抑制需要の差のことなので, 2つの長方形の値の最小値をつかえばよい.

ミス

長方形を分割していくのは再起関数で書くと楽ですね.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = max(a, b);
#define chmin(a, b) a = min(a, b);
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int h, w, s;
int U[35][35];
int allsum = 0;
int sum[35][35];
// dp[y1][x1][y2][x2] := 左上(y1, x1), 右下(y2, x2)の長方形を考えた時の, 
// グループの分け方の最大数, 最大の予備力
pair<int, int> dp[35][35][35][35];

void sum2D(int h, int w) {
    rep(y, h + 1)rep(x, w + 1) sum[y][x] = 0;
    rep(y, h)rep(x, w) sum[y + 1][x + 1] = U[y][x]; // まずは埋め込む
    rep(y, h + 1)rep(x, w) sum[y][x + 1] += sum[y][x]; // 横
    rep(y, h)rep(x, w + 1) sum[y + 1][x] += sum[y][x]; // 縦
}
int calcSum(int y1, int x1, int y2, int x2) {
    return sum[y2 + 1][x2 + 1] - sum[y2 + 1][x1] - sum[y1][x2 + 1] + sum[y1][x1];
}

pair<int, int> dfs(int y1, int x1, int y2, int x2) {
    if(dp[y1][x1][y2][x2] != make_pair(0, INF)) return dp[y1][x1][y2][x2];
    
    auto ret = make_pair(1, s - (allsum - calcSum(y1, x1, y2, x2))); // これ以上分割できない場合の値

    for (int i = x1; i < x2; ++i){
        if(s - (allsum - calcSum(y1, x1, y2, i)) < 0) continue;
        if(s - (allsum - calcSum(y1, i + 1, y2, x2)) < 0) continue;
        auto ret1 = dfs(y1, x1, y2, i);
        auto ret2 = dfs(y1, i + 1, y2, x2);
        chmax(ret, make_pair(ret1.fi + ret2.fi, min(ret1.se, ret2.se)));
    }

    for (int i = y1; i < y2; ++i){
        if(s - (allsum - calcSum(y1, x1, i, x2)) < 0) continue;
        if(s - (allsum - calcSum(i + 1, x1, y2, x2)) < 0) continue;
        auto ret1 = dfs(y1, x1, i, x2);
        auto ret2 = dfs(i + 1, x1, y2, x2);
        chmax(ret, make_pair(ret1.fi + ret2.fi, min(ret1.se, ret2.se)));
    }
    return dp[y1][x1][y2][x2] = ret;
}

int main(void) {
    while(1) {
        scanf("%d %d %d", &h, &w, &s);

        if(h == 0 && w == 0 && s == 0) break;
        rep(i, h)rep(j, w) scanf("%d", &U[i][j]);
        allsum = 0;
        rep(i, h)rep(j, w) allsum += U[i][j];
        sum2D(h, w);
        rep(i, 35)rep(j, 35)rep(k, 35)rep(l, 35) dp[i][j][k][l] = make_pair(0, INF);
        auto ans = dfs(0, 0, h - 1, w - 1);
        printf("%d %d\n", ans.fi, ans.se);
    }
    return 0;
}

Codeforces #223 Div1. C. Sereja and Brackets

問題

問題概要

‘('と’)‘が含まれた文字列が与えられる. その文字列のl番目からからr番目のまでの文字を考えたときに, その中にカッコの対応が最大でいくつできるかを書くクエリごとに答える.

解法

segtreeを使えばよい. 状態として区間[l, r)の中で,
すでにカッコの対応が作られている文字の数
まだ使われていない ‘(’ の数
また使われていない ‘)’ の数
を持つようにすればよい.
演算は左の区間の'(‘ の数と, 右の区間の’)‘の数の最小値の2倍をその区間で対応付けられたカッコの数に足せばよい. 例えば左の区間が )(())( で, 右の区間が )()() の場合, 左はすでに対応付けられているのが4, ’(‘が1, ’)‘が1となっている. 右はすでに対応付けられているのが4, ’)‘が1, ’(‘が0となっている.
新たに対応付けられるのは, 左の’(‘の数, 右の’)‘の数の最小値なので,1組となる. よって, 演算の結果は,  すでに対応付けられているのが, 8, ’(‘が 0, ’)‘が 1となっている.
また, 非可換なので演算の順番に注意.

ミス

左右の区間を見てすでにカッコの対応が付いているものは, 使われていない部分だけで新たにカッコの対応が作れるかを考えればよいということに気づくのに時間がかかる.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

template <class T> //T(モノイド) : dat[]の中身の型
class segtree{
public:
    int n;
    T neutral;
    vector<T> dat;
    T func(T l, T r) { //二項演算子
        int lok, lopen, lclose, rok, ropen, rclose;
        tie(lok, lopen, lclose) = l;
        tie(rok, ropen, rclose) = r;
        int add = min(lopen, rclose);
        return make_tuple(lok + rok + 2 * add, lopen + ropen - add, lclose + rclose - add);
    }
    segtree(int n_, T val): n(n_), neutral(val) { //n_:要素数 val:単位元
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, neutral); //初期値
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        k += n - 1;
        dat[k] = val;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r) { //[a, b)の区間
        if(r <= a || b <= l) return neutral;
        if(a <= l && r <= b) return dat[k];
        else {
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return func(vl, vr);
        }
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};


int m, l[100010], r[100010];
int main(void) {
    string s; cin >> s;
    segtree<tuple<int, int, int>> seg(s.size(), make_tuple(0, 0, 0));
    rep(i, s.size()) {
        if(s[i] == '(') seg.update(i, make_tuple(0, 1, 0));
        else seg.update(i, make_tuple(0, 0, 1));
    }

    scanf("%d", &m);
    rep(i, m) scanf("%d %d", &l[i], &r[i]);
    rep(i, m){
        auto ret = seg.query(l[i] - 1, r[i]);
        int a, b, c; tie(a, b, c) = ret;
        printf("%d\n", a);
    }
    return 0;
}