intさわだんのBlack History

刹那的レジェンドになりたい。

ICPC 模擬国内予選2007B 大崎 AOJ 2013

ICPC模擬国内予選

まず到着時間が早いもの順にソートする。

それぞれの時間をソートした順にみていき、その時間に運行できる電車があればそのなかで一番最後に到着するものを採用し、なければ新しく電車を使う。

電車の合計数が答え。

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> P;


int times[10010][2];
int train[10010];

int main(){
		int n;
		while(true){
				vector<pair<int,int> > times;
				cin >> n;
				if(n == 0)break;
				for(int i = 0;i < n;i++){
						int a1,a2,a3,b1,b2,b3;
						scanf("%d:%d:%d %d:%d:%d",&a1,&a2,&a3,&b1,&b2,&b3);
						int a = a3 + a2*100 + a1*10000,b = b3 + b2*100 + b1*10000;
						times.push_back(P(b,a));
				}
				sort(times.begin(),times.end());
				vector<int> train;
				train.push_back(0);
				for(int i = 0;i < n;i++){
						int ban=-1,mintime = 1000000;
						for(int j = 0;j < train.size();j++){
								int diff = times[i].second - train[j];
								if(diff >= 0 && diff < mintime){
										mintime = diff;
										ban = j;
								}
						}
						if(ban == -1){
								train.push_back(times[i].first);
						}else{
								train[ban] = times[i].first;
						}
				}
				cout << train.size() << endl;
		}
}

ICPC 模擬国内予選2010C 差分パルス符号変調 AOJ 2199

ICPC模擬国内予選 DP

簡単なDP。5秒考えればわかる。

#include <bits/stdc++.h>
using namespace std;

#define INF 2000000000

int dp[20010][260];
int c[20],x[20010];

int main(){

    int n,m;

    while(true){
        cin >> n >> m;
        if(n + m == 0)break;
        for(int i = 0;i < m;i++)cin >> c[i];
        for(int i = 0;i < n;i++)cin >> x[i];
        for(int i = 0;i < n+1;i++){
            for(int j = 0;j < 257;j++){
                dp[i][j] = INF;
            }
        }       
        dp[0][128] = 0;

        for(int i = 0;i < n;i++){
            for(int j = 0;j <= 255;j++){
                for(int k = 0;k < m;k++){
                    int ne = j + c[k];
                    ne = max(ne,0);
                    ne = min(255,ne);
                    dp[i+1][ne] = min(dp[i+1][ne], dp[i][j] + (x[i]-ne)*(x[i]-ne) );
                //    if(dp[i+1][ne] != INF)printf("dp[%d][%d] = %d\n",i+1,ne,dp[i+1][ne]);
                }
            }
        }
        int ans = INF;
        for(int i = 0;i <= 255;i++) ans = min(ans,dp[n][i]);
        cout << ans << endl;
    }
    return 0;
}

ICPC 模擬国内2005F Gather the Maps AOJ 2011

STLゲー

問題文
judge.u-aizu.ac.jp

解法は自明なので書きません
setを乱用すれば簡単に解ける

#include <bits/stdc++.h>

using namespace std;

int n;
bool day[35][55];

int main(){
    while(true){
        cin >> n;
        if(n == 0)break;

        for(int i = 1;i <= n;i++){
            int f;
            cin >> f;
            for(int j = 0;j < 33;j++)day[j][i] = false;
            for(int j = 0;j < f;j++){
                int tmp;
                cin >> tmp;
                day[tmp][i] = true;
            }
        }
        set<int> s[33][55];
        for(int i = 1;i <= n;i++)s[0][i].insert(i);
        int ans = -1;
        for(int i = 1;i <= 30;i++){
            for(int j = 1;j <= n;j++){
                for(auto itr = s[i-1][j].begin(); itr != s[i-1][j].end(); ++itr){
                    s[i][j].insert(*itr);
                }
            }
            set<int> tmps;
            for(int j = 1;j <= n;j++){
                if(day[i][j] == false)continue;
                for(auto itr = s[i][j].begin(); itr != s[i][j].end();++itr){
                    tmps.insert(*itr);
                }
            }
            if(tmps.size() == n){
                ans = i;
                break;
            }
            for(int j = 1;j <= n;j++){
                if(day[i][j] == false)continue;
                for(auto itr = tmps.begin();itr != tmps.end();++itr){
                    s[i][j].insert(*itr);
                }
            }
        }
        cout << ans << endl;
    }
}

ICPC 模擬国内2007D スクウェア・ルート AOJ2015

STLゲー

judge.u-aizu.ac.jp

あらかじめ考えられるすべての辺の長さをキーに、その長さの出現回数を値にして保存しておけばよい。大きめの配列を使えばいいがmapを使った。

#include <bits/stdc++.h>

using namespace std;


int n,m;
int h[1600],w[1600];


int main(){
    while(true){
        cin >> n >> m;
        if(n + m == 0)break;
        for(int i = 1;i <= n;i++)cin >> h[i];
        for(int j = 1;j <= m;j++)cin >> w[j];
        map<int, int> d;
        for(int i = 1;i <= m;i++){
            int sum = 0;
            for(int j = i;j <= m;j++){
                sum += w[j];
                d[sum]++;
            }
        }
        int ans = 0;
        for(int i = 1;i <= n;i++){
            int sum = 0;
            for(int j = i;j <= n;j++){
                sum += h[j];
                ans += d[sum];
            }
        }
        cout << ans << endl;
    }
}

AOJ 0178 テトリス

PCK予選

reading-hard　＆　実装に工夫が必要

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int n;
int h[7];
bool m[6010][7];
int b[1010][5];

int main()
{
    while (true)
    {
        cin >> n;
        if (n == 0)
            break;
        for (int i = 0; i < 5500; i++)
        {
            for (int j = 0; j < 7; j++)
                m[i][j] = false;
        }
        for (int i = 0; i <= 6; i++)
        {
            h[i] = 0;
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                cin >> b[i][j];
                if (j == 1)
                {
                    ans += b[i][j];
                }
            }
        }
        for(int i = 0;i < n;i++){
            if(b[i][0] == 1){
                int hmax = h[b[i][2]];
                for(int j = 0;j < b[i][1];j++){
                    hmax = max(hmax,h[b[i][2]+j]);
                }
                hmax++;
                for(int j = 0;j < b[i][1];j++){
                    h[b[i][2]+j] = hmax;
                    m[hmax][b[i][2]+j] = true;
                }
            }else{
                int hmax = h[b[i][2]];
                for(int j = 1;j <= b[i][1];j++){
                    m[hmax+j][b[i][2]] = true;
                }
                h[b[i][2]] = hmax + b[i][1];
            }
            int hmax = h[1];
            for(int j = 1;j <= 5;j++) hmax = max(hmax,h[j]);
            set<int> s;
            for(int j = 1;j <= hmax;j++){
                int count = 0;
                for(int k = 1;k <= 5;k++)if(m[j][k] == true)count++;
                if(count == 5){
                    ans -= 5;
                    s.insert(j);
                }
            }
            int nj = 1;
            for(int j = 1;j <= hmax;j++){
                if( s.find(j) != s.end() )continue;
                for(int k = 1;k <= 5;k++){
                    m[nj][k] = m[j][k];
                }
                nj++;
            }
            for(int j = nj;j < 5050;j++){
                for(int k = 1;k <= 5;k++)m[j][k] = false;
            }
            for(int j = 1;j <= 5;j++){
                h[j] = 0;
                for(int k = hmax;k >= 0;k--){
                    if(m[k][j] == true){
                        h[j] = k;
                        break;
                    }
                }
            }
        }
        int hmax = h[1];
        for(int j = 1;j <= 5;j++) hmax = max(hmax,h[j]);
        for(int j = hmax;j >= 1;j--){
        }
        cout << ans << endl;
    }
}

ICPC 国内予選2012E 鎖中経路 AOJ1183

DP ICPC国内予選

問題文
judge.u-aizu.ac.jp


パッと見DP感があるな～と思って少し考えたらほんとにDPだった。
解説：
i番目の円とi+1番目の円の交点は2つある。その二つの交点に適当に0個目、1個目の点とすると。
dp[i][j] =0番目の円（一番端の円）から、 i番目の円とi+1番目のj(=0,1)個目の交点にたどり着くまでの最小の長さ
と定義できて、それを典型的なDPで回せば求まる。
if(0~iの0,1個目の交点から今の点までの線分が、任意の円に重なっている場合) dp[i][j] = min( dp[0~i][0,1] + （0~iの0,1個目の交点から今の点までの距離） )
で求められる。
if文の判定は線分の交差判定をぶん回せばよい

dist関数の引数をint型にするという珍プレーをして無限に時間を消費したので気を付けていきたい（まあライブラリを使えばこういうミスはないと思うが、）

#include <bits/stdc++.h>

using namespace std;


#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
 
struct Point{
    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 norm() {return x * x + y * y; }
    double abs() {return sqrt(norm()); }
 
    bool operator < (const Point &p) const{
        return (x != p.x ? x < p.x : y < p.y);
    }
 
    bool operator == (const Point &p) const{
        return (fabs(x - p.x) < EPS && fabs(y - p.y) < EPS);
    }
};
 
typedef Point Vector;
 
struct Circle{
    Point c;
    double r;
 
    Circle(Point c = Point(), double r = 0.0): c(c), r(r) {}
};
 
double norm(Vector a){
    return a.x * a.x + a.y * a.y;
}
 
double abs(Vector a){
    return sqrt(norm(a));
}
 
double arg(Vector p){
    return atan2(p.y, p.x);
}
 
Vector polar(double a, double r){
    return Point(cos(r) * a, sin(r) * a);
}
 
pair<Point, Point> getCrossPoints(Circle c1, Circle c2){
    double d = abs(c1.c - c2.c);
    double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
    double t = arg(c2.c - c1.c);
    return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a));
}

int n;

double dist(double x1,double y1,double x2,double y2){
    return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)  );
}

bool judgeIenter(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy) {
    double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
    double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
    double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
    double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);

   // return (tc * td < 0 && ta * tb < 0); //端点を含まない場合
     return (tc * td <= 0 && ta * tb <= 0); // 端点を含む場合
}
double INF = 10000000;
double dp[110][2];
double d[110][3];
double p[110][2][2];
bool check(int a,int aa,int b,int bb){
    double ax,ay,bx,by;
    if(a == -1){
        ax = d[0][0];
        ay = d[0][1];
    }else{
        ax = p[a][aa][0];
        ay = p[a][aa][1];
    }
    if(b == n-1){
        bx = d[n-1][0];
        by = d[n-1][1];
    }else{
        bx = p[b][bb][0];
        by = p[b][bb][1];
    }
    bool flag = true;
    for(int i = max(0,a);i < b;i++){
        if(judgeIenter(ax,ay,bx,by,p[i][0][0],p[i][0][1],p[i][1][0],p[i][1][1]) == false){
            flag = false;
            break;
        } 
    }
    
    return (flag);
}



int main(){
    while(true){
        cin >> n;
        if(n == 0)break;
        for(int i = 0;i <= n+1;i++){
            dp[i][0] = INF;
            dp[i][1] = INF;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 3;j++){
                cin >> d[i][j];
            }
        }
        for(int i = 0;i < n-1;i++){
            Circle c1 = {Point(d[i][0], d[i][1]), d[i][2]};
            Circle c2 = {Point(d[i+1][0], d[i+1][1]), d[i+1][2]};
            pair<Point, Point> ansp = getCrossPoints(c1, c2);
            p[i][0][0] = ansp.first.x;
            p[i][0][1] = ansp.first.y;
            p[i][1][0] = ansp.second.x;
            p[i][1][1] = ansp.second.y;
        }
        for(int i = 0;i < 2;i++){
            dp[0][i] = dist(d[0][0],d[0][1],p[0][i][0],p[0][i][1]);
        }
        
        for(int i = 1;i < n-1;i++){
            for(int k = 0;k < 2;k++){
                double nx = p[i][k][0],ny = p[i][k][1];
                if(check(-1,0,i,k)) dp[i][k] = dist(d[0][0],d[0][1],nx,ny);
                for(int j = 0;j < i;j++){
                    for(int kk = 0;kk < 2;kk++){
                        if(check(j,kk,i,k))dp[i][k] = min(dp[i][k],dp[j][kk]+dist(p[j][kk][0],p[j][kk][1],nx,ny));
                    }
                }
            }
        }
        double ans = INF;
        for(int i = -1;i < n-1;i++){
            for(int k = 0;k < 2;k++){
                if(check(i,k,n-1,0)){
                    if(i == -1)ans = min(ans,dist(d[0][0],d[0][1],d[n-1][0],d[n-1][1]));
                    else ans = min(ans,dp[i][k]+dist(p[i][k][0],p[i][k][1],d[n-1][0],d[n-1][1]));
                }
            }
        }
        printf("%lf\n",ans);
    }
}

ICPC 国内予選2016E　3Dプリント　AOJ1612

ICPC国内予選 グラフ

問題↓
judge.u-aizu.ac.jp



解説

  • 「各立方体は 0 個，1 個 または 2 個の立方体と重なることがあるが，3 個以上とは重ならない．」という条件から各立方体は鎖状もしくは環状になることがわかる。
  • 任意の二つの立方体が重なるかどうかは少し考えればわかる（説明がめんどいので書かない）
  • 重なりうる二つの立方体が重なった場合、どれだけの表面積を節約できるのかを求め配列に保存しておく。
  • あとはその配列の情報を用いて、対象とするk個のつながった直方体の表面積を求め、それをひとつづつずらしていきその中の最小値を求めればよい。（ずらしていくときにqueueを使った）
  • 頭が悪かったので鎖状のものと環状のものを同様に処理できなかったため、わざわざ似たような二つの処理を書いた。（グラフ慣れしていればいい感じに実装できそう）
#include <bits/stdc++.h>

using namespace std;

int INF = 1e9;

int xyz[2010][3];
int d[2010][2010];
bool ch[2010];

int main(){
    int n,k,s;

    while(true){
        cin >> n >> k >> s;
        int plus = (s*s) * 6;
        if(n == 0)break;

        vector<int> G[2010];
        int ans = INF;
        for(int i = 0;i < n;i++){
            ch[i] = false;
            for(int j = 0;j < 3;j++){
                cin >> xyz[i][j];
            }
        }

        if(k == 1){
            cout << (s*s)*6 << endl;
            continue;
        }   
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                d[i][j] = -1;
            }
        }    
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(i == j) continue;
                if(xyz[i][2] > xyz[j][2])continue;
                if(xyz[i][2] == xyz[j][2] && i > j)continue;

                if(xyz[i][2]+s >= xyz[j][2] && xyz[i][0]-s <= xyz[j][0] && xyz[i][0]+s >= xyz[j][0]
                    && xyz[i][1]-s <= xyz[j][1] && xyz[i][1]+s >= xyz[j][1]){
                        G[i].push_back(j);
                        G[j].push_back(i);
                        int xx;
                        int yy;
                        if(xyz[i][0] < xyz[j][0]){
                            xx = xyz[i][0]+s - xyz[j][0];
                        }else{
                            xx = xyz[j][0]+s - xyz[i][0];
                        }
                        if(xyz[i][1] < xyz[j][1]){
                            yy = xyz[i][1]+s-xyz[j][1];
                        }else{
                            yy = xyz[j][1]+s-xyz[i][1];
                        }
                        int zz = xyz[i][2]+s-xyz[j][2];
                       
                        d[i][j] = 2 * ( xx*zz + yy*zz + xx*yy);
                        d[j][i] = d[i][j];
                    }
            }
        }

        for(int i = 0;i < n;i++){
            if(ch[i] == true)continue;
            if(G[i].size() == 1){
                ch[i] = true;
                int now = i;
                int pre = -1;
                int count = 1;
                int sum = plus;
                queue<int> que;
                while(true){
                    if(count == k){
                        ans = min(ans,sum);
                        bool flag = true;
                        for(int j = 0;j < G[now].size();j++){
                            if(pre != G[now][j] && ch[G[now][j]] == false){
                                pre = now;
                                now = G[pre][j];
                                ch[now] = true;
                                flag = false;
                                break;
                            }
                        }
                        if(flag)break;
                        int q = que.front(); que.pop();
                        que.push(d[pre][now]);
                        sum += q;
                        sum -= d[pre][now];
                        ans = min(ans,sum);
                    }else{
                        sum += plus;
                        count++;
                        bool flag = true;
                        for(int j = 0;j < G[now].size();j++){
                            if(pre != G[now][j] && ch[G[now][j]] == false){
                                pre = now;
                                now = G[pre][j];
                                ch[now] = true;
                                flag = false;
                                break;
                            }
                        }
                        if(flag)break;
                        que.push(d[pre][now]);
                        sum -= d[pre][now];
                    }
                }
            }
        }
        
        for(int i = 0;i < n;i++){
            if(ch[i] == true)continue;
            if(G[i].size() != 2)continue;
            ch[i] = true;
            int count = 1;
            int now = i;
            int pre = -1;
            int sum = (s*s)*6;
            queue<int> que;
            queue<int> num;
            num.push(-1);
            while(true){
                if(count == k){
                    ans = min(ans,sum);
                    int q = num.front(); num.pop();
                    if(q == -1 && d[now][i] != -1 && k != 2){
                        ans = min(ans,sum-d[now][i]);
                        break;
                    } 
                    if(q == i)break;
                    for(int j = 0;j < G[now].size();j++){
                        if(pre != G[now][j]){
                            pre = now;
                            now = G[pre][j];
                            que.push(d[now][pre]);
                            num.push(now);
                            ch[now] = true;
                            break;
                        }
                    }
                    q = que.front(); que.pop();
                    sum += q;
                    sum -= d[now][pre];
                    ans = min(ans,sum);
                }else{
                    count++;
                    bool endflag = false;
                    for(int j = 0;j < G[now].size();j++){
                        if(pre != G[now][j]){
                            
                            pre = now;
                            now = G[pre][j];
                            if(now == i){
                                endflag = true;
                                break;
                            }
                            que.push(d[now][pre]);
                            num.push(now);
                            ch[now] = true;
                            break;
                        }
                    }
                    if(endflag)break;
                    sum += plus;
                    sum -= d[now][pre];
                }
            }
        }
        if(ans == INF){
            cout << -1 << endl;
        }else{
            cout << ans << endl;
        }
    }
}

ICPC 国内予選2010D ぐらぐら AOJ1168

ICPC国内予選

解説（文章にするのがめんどくさいので箇条書きで書きます）

  • 最初の入力では数字が1~9の範囲しかなく、ピースが10個以上の時に区別が難しいのでO(WH)で番号を振りなおす。（これによってピースが合計何個あるのかもわかる）
  • 次にそれぞれのピースについて、下に接するブロックの右端の座標(XL)、左端の座標(XR)、重さの総和、下には何番目のピースがあるのか（これはvectorに保存しておく）を求め、それぞれ配列に保存する
  • 最後にそれぞれのピースについてSTABLEかどうかを確認していき、一つでのUNSTABLEなピースがあればUNSTABLEとすればよい。具体的にどう確認するかというと、再帰（深さ優先探索）で自分の上にあるピースの重さの総和とブロックの数の総和をもとめそれらの数値から重心のx座標をもとめそれをXL、XRと比較すればよい。

解法は自明なのだがそれを時間内にミスなく実装するとなるとなかなか難しいので経験の差が出てくる問題なのかもしれない。

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

typedef pair<double, int> PD;

 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

bool ch[65][15];
int num[65][15];
int w,h;
double wei[160];
int x[160][2]; // 0:Xl,1:Xr
vector<int> v[160];



void find(int x,int y,int count){
    int sum = 1;
    queue<P> que;
    que.push(P(x,y));
    while(!que.empty()){
        if(sum == 4)break;
        P q = que.front(); que.pop();
        for(int k = 0;k < 4;k++){
            int nx = q.fs + dx[k],ny = q.sc + dy[k];
            if(nx < 0 || ny < 0 || nx >= h || ny >= w)continue;
            if(ch[nx][ny] == false && num[x][y] == num[nx][ny]){
                sum++;
                ch[nx][ny] = true;
                num[nx][ny] = count;
                que.push(P(nx,ny));
            }
        }
    }
}

PD get_weight(int k){
    double wsum = wei[k];
    int sec = 4;
    for(int i = 0;i < v[k].size();i++){
        PD p = get_weight(v[k][i]);
        wsum += p.fs;
        sec += p.sc;
    }
    return (PD(wsum,sec));
}

int main(){
    while(true){
        cin >> w >> h;
        if(w == 0)break;
        for(int i = 0;i < h;i++){
            char tmp[20];
            cin >> tmp;
            for(int j = 0;j < w;j++){
                ch[i][j] = false;
                if(tmp[j] == '.'){
                    num[i][j] = 0;
                    ch[i][j] = true;
                }else{
                    num[i][j] = tmp[j] - '0';
                }
            }
        }
        for(int j = 0;j < w;j++) num[h][j] = 0;
        int count = 0;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                if(ch[i][j] == false){
                    ch[i][j] = true;
                    count++;
                    find(i,j,count);
                    num[i][j] = count;
                }
            }
        }

        for(int k = 1;k <= count;k++){
            wei[k] = 0.0;
            int und=0;
            int a=100,b=-1;
            for(int i = 0;i < h;i++){
                for(int j = 0;j < w;j++){
                    if(num[i][j] != k) continue;
                    wei[k] += (double) j + 0.5;
                    if((num[i+1][j] >= 1 && num[i+1][j] != k) || i == h-1){
                        und = num[i+1][j];
                        a = min(a,j);
                        b = max(b,j+1); 
                    }
                }
            }
            v[und].push_back(k);
            x[k][0] = a;
            x[k][1] = b;
        }
        bool ans = true;
        for(int i = 1;i <= count;i++){
            PD p = get_weight(i);
            if(x[i][0] >= p.fs/(double)p.sc || x[i][1] <= p.fs/(double)p.sc){
                ans = false;
                break;
            }
        }
        if(ans){
            cout << "STABLE" << endl;
        }else{
            cout << "UNSTABLE" << endl;
        }
        for(int i = 0;i <= count;i++)  v[i].clear();
    }
}

ICPC 国内予選2008E 大玉転がし AOJ 1157

ICPC国内予選 幾何

解説:

まずそれぞれの障害物について、直線状のコースへの距離の最小値を求める。（つまり、障害物とコースの間の一番短くなるときの距離を求める）。これについては、点と線分の距離を用いて求める。ライブラリについては下記のサイトを参照しました。
qiita.com


また、コースの線分と障害物の周りの長方形の線分（４つある）が交差している場合、コース上に障害物があることになるのでこのときのansは0になる。ここについては下記のサイトを参照しました。
qiita.com


あとはコースと障害物の間の距離と、障害物の高さの情報から各障害物について大玉の最大値が求められるので（２パターンの場合分けが必要。すこし考えればわかるのでここでは自明とする）そのなかの最小値がans。

また、障害物のなかにコースがスッポリ入るというコーナーケースもあるので注意。（ただし、親切なことにサンプルにそのような入力例があるので気づきやすい）



#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1,0,-1,-1,-1,0,1,1};
int dy[]={1,1,1,0,-1,-1,-1,0};

double block[55][4];
double h[55];
int n;
double sx,sy,ex,ey;

double min_d2(double x0,double y0,double x1,double y1,double x2,double y2) {
    double a = x2 - x1;
    double b = y2 - y1;
    double a2 = a * a;
    double b2 = b * b;
    double r2 = a2 + b2;
    double tt = -(a*(x1-x0)+b*(y1-y0));
    if( tt < 0 ) {
        return ( (x1-x0)*(x1-x0) + (y1-y0)*(y1-y0) );
    }
    if( tt > r2 ) {
        return ( (x2-x0)*(x2-x0) + (y2-y0)*(y2-y0) );
    }
    double f1 = a*(y1-y0)-b*(x1-x0);
    return ( (f1*f1)/r2 );
}

bool judgeIenter(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy) {
    double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
    double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
    double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
    double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);

    return (tc * td < 0 && ta * tb < 0);
    // return tc * td <= 0 && ta * tb <= 0; // 端点を含む場合
}

double dist(int m){
    bool flag = false;
    double b[4];
    for(int k = 0;k < 4;k++) b[k] = block[m][k];
    flag = ( judgeIenter(sx,sy,ex,ey,b[0],b[1],b[0],b[3]) || flag );
    flag = ( judgeIenter(sx,sy,ex,ey,b[0],b[1],b[2],b[1]) || flag );
    flag = ( judgeIenter(sx,sy,ex,ey,b[0],b[3],b[2],b[3]) || flag );
    flag = ( judgeIenter(sx,sy,ex,ey,b[2],b[1],b[2],b[3]) || flag );
    if(flag)return 0;
    double ret = min_d2(b[0],b[1],sx,sy,ex,ey);
    ret = min(ret,min_d2(b[0],b[3],sx,sy,ex,ey));
    ret = min(ret,min_d2(b[2],b[1],sx,sy,ex,ey));
    ret = min(ret,min_d2(b[2],b[3],sx,sy,ex,ey));

    ret = min(ret,min_d2(sx,sy,b[0],b[1],b[0],b[3]));
    ret = min(ret,min_d2(sx,sy,b[0],b[1],b[2],b[1]));
    ret = min(ret,min_d2(sx,sy,b[0],b[3],b[2],b[3]));
    ret = min(ret,min_d2(sx,sy,b[2],b[1],b[2],b[3]));

    ret = min(ret,min_d2(ex,ey,b[0],b[1],b[0],b[3]));
    ret = min(ret,min_d2(ex,ey,b[0],b[1],b[2],b[1]));
    ret = min(ret,min_d2(ex,ey,b[0],b[3],b[2],b[3]));
    ret = min(ret,min_d2(ex,ey,b[2],b[1],b[2],b[3]));
    return sqrt(ret);
}

int main(){
    
    while(true){
        cin >> n;
        if(n == 0)break;
        cin >> sx >> sy >> ex >> ey;
        if(sx > ex){
            int tmpx = sx,tmpy = sy;
            sx = ex;
            sy = ey;
            ex = tmpx;
            ey = tmpy;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 4;j++){
                cin >> block[i][j];
            }
            cin >> h[i];
        }
        double ans = 1000;
        for(int i = 0;i < n;i++){
            double d = dist(i);
    //        cout << i << ":" << d << endl;
            if(d == 0){
                ans = 0;
                break;
            }
            if(block[i][0] <= sx && block[i][2] >= ex && block[i][1] <= min(sy,ey) && block[i][3] >= max(sy,ey)){
                ans = 0;
                break;
            }
            double tmpans;
            if(d <= h[i]){
                tmpans = d;
            }else{
                tmpans = (d*d + h[i]*h[i]) / (2*h[i]);
            }
            if(ans > tmpans) ans = tmpans;
        }
        printf("%f\n",ans);
    //    cout << ans << endl;
    }
}

ICPC 国内予選2004D Circle and Points AOJ1132

ICPC国内予選 幾何

解法：

  • 任意の二点を選ぶ(N*N通り）
  • その二点が円周上にくるような半径１の円の中心の座標を求める。（二点間の距離が２以上の時はそのような円は存在しないのでスキップ）
  • その円にいくつの点が含まれているか計算量Nで求める。その最大値が答え。

計算量O(N^3)

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

double p[305][2];
int n;

double dist(int a,int b){
    return sqrt((p[a][0]-p[b][0])*(p[a][0]-p[b][0])+(p[a][1]-p[b][1])*(p[a][1]-p[b][1]));
}

double get_o(int i,double st,double en,double th,double b){
    double diff = 1.0;
    while(diff > 0.00001){
        double half[2];
        half[0] = (en+st)/2.0;
        half[1] = th*half[0] + b;
        if( (p[i][0]-half[0])*(p[i][0]-half[0]) + (p[i][1]-half[1])*(p[i][1]-half[1]) >1){
            en = half[0];
        }else{
            st = half[0];
        }
        diff = en - st;
        if(diff < 0 ) diff = -1.0 * diff;
    }
  //  cout << "st:" << st << ", en:" << en << endl;
    return st;
}

int find_ans(double x,double y,int a,int b){
    int ans = 2;
    for(int i = 0;i < n;i++){
        if(i == a || i == b)continue;
        if( (p[i][0]-x)*(p[i][0]-x) + (p[i][1]-y)*(p[i][1]-y) <= 1.0) ans++;
    }
    return ans;
}

int main(){
    while(true){
        cin >> n;
        if(n == 0)break;
        for(int i = 0;i < n;i++){
            cin >> p[i][0] >> p[i][1];
        }
        int ans = 1;
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                double d = dist(i,j);
                if(d > 2.0)continue;
                if(true){
            //    if(p[i][1] != p[j][1]){
                    double th = -(p[j][0]-p[i][0])/(p[j][1]-p[i][1]);
                    double half[2];
                    half[0] = (p[i][0]+p[j][0])/2.0;
                    half[1] = (p[i][1]+p[j][1])/2.0;
                    double b = half[1] - th*half[0];
                    double o[2];
                    o[0] = get_o(i,half[0],half[0]+1,th,b);
                    o[1] = th*o[0] + b;
                //    cout << "x1:" << p[i][0] << ",y1" << p[i][1] << ",x2" << p[j][0] << ",y2" << p[j][1] << ",ox" << o[0] << ",oy" << o[1] << endl;
                    ans = max(ans,find_ans(o[0],o[1],i,j));
                    o[0] = get_o(i,half[0],half[0]-1,th,b);
                    o[1] = th*o[0] + b;
                //    cout << "x1:" << p[i][0] << ",y1" << p[i][1] << ",x2" << p[j][0] << ",y2" << p[j][1] << ",ox" << o[0] << ",oy" << o[1] << endl;
                    ans = max(ans,find_ans(o[0],o[1],i,j));
                }
            }
        }
        cout << ans << endl;
    }
}