SRM 210 DIV1 Hard NegativePhotoresist

問題 Editorial

問題

略

解答

二分探索する

コメント

簡単なのにバグらせて無駄に時間かかってしまった

コード

#include <string>
#include <vector>
#include <sstream>
#include <cstring>
#include <limits>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))

using namespace std;
typedef vector<pair<int,int> > vpii;

struct NegativePhotoresist {
	double minimumTilt(vector <string> pinConnections, int limit) {
		vpii v;
		static bool c[55][55];
		mset(c, 0);
		int n = pinConnections.size();
		each(i, pinConnections) {
			each(j, *i) if(*j == ',') *j =' ';
			stringstream ss(*i);
			int x, y;
			ss >> x >> y;
			v.pb(mp(x, y));
			int t;
			while(ss >> t) c[i - pinConnections.begin()][t] = true;
		}
		const double inf = numeric_limits<double>::infinity();
		double l = 0, u = acos(-1) / 2.;
		rep(ii, 100) {
			double m = (l + u) / 2.;
			double s = cos(m);
			vector<complex<double> > w;
			rep(i, n) w.pb(complex<double>(v[i].first * 1., v[i].second * s));
			static double wf[55][55];
			rep(i, n) rep(j, n) wf[i][j] = inf;
			rep(i, n) wf[i][i] = 0;
			rep(i, n) rep(j, n) if(c[i][j]) wf[i][j] = min(wf[i][j], abs(w[i] - w[j]));
			rep(k, n) rep(i, n) rep(j, n) wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);
			double sum = 0;
			rep(i, n) reu(j, i+1, n) if(wf[i][j] != inf) {
				sum += wf[i][j];
			}
			if(sum <= limit) u = m;
			else l = m;
		}
		return u;
	}
};