Submission #1000976

---

Source Code Expand

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;

#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;
     // Two-phase simplex algorithm for solving linear programs of the form
     //
     //     maximize     c^T x
     //     subject to   Ax <= b
     //                  x >= 0
     //
     // INPUT: A -- an m x n matrix
     //        b -- an m-dimensional vector
     //        c -- an n-dimensional vector
     //        x -- a vector where the optimal solution will be stored
     //
     // OUTPUT: value of the optimal solution (infinity if unbounded
     //         above, nan if infeasible)
     //
     // To use this code, create an LPSolver object with A, b, and c as
     // arguments.  Then, call Solve(x).

     typedef ld DOUBLE;
     typedef vector<DOUBLE> VD;
     typedef vector<VD> VVD;
     typedef vector<int> VI;

     const DOUBLE EPS = 1e-12;

     struct LPSolver {
       int m, n;
       VI B, N;
       VVD D;

       LPSolver(const VVD &A, const VD &b, const VD &c) :
         m(b.size()), n(c.size()), N(n + 1), B(m), D(m + 2, VD(n + 2)) {
         for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
         for (int i = 0; i < m; i++) { B[i] = n + i; D[i][n] = -1; D[i][n + 1] = b[i]; }
         for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
         N[n] = -1; D[m + 1][n] = 1;
       }

       void Pivot(int r, int s) {
         for (int i = 0; i < m + 2; i++) if (i != r)
           for (int j = 0; j < n + 2; j++) if (j != s)
             D[i][j] -= D[r][j] * D[i][s] / D[r][s];
         for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] /= D[r][s];
         for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] /= -D[r][s];
         D[r][s] = 1.0 / D[r][s];
         swap(B[r], N[s]);
       }

       bool Simplex(int phase) {
         int x = phase == 1 ? m + 1 : m;
         while (true) {
           int s = -1;
           for (int j = 0; j <= n; j++) {
             if (phase == 2 && N[j] == -1) continue;
             if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j;
           }
           if (D[x][s] > -EPS) return true;
           int r = -1;
           for (int i = 0; i < m; i++) {
             if (D[i][s] < EPS) continue;
             if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
               (D[i][n + 1] / D[i][s]) == (D[r][n + 1] / D[r][s]) && B[i] < B[r]) r = i;
           }
           if (r == -1) return false;
           Pivot(r, s);
         }
       }

       DOUBLE Solve(VD &x) {
         int r = 0;
         for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
         if (D[r][n + 1] < -EPS) {
           Pivot(r, n);
           if (!Simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<DOUBLE>::infinity();
           for (int i = 0; i < m; i++) if (B[i] == -1) {
             int s = -1;
             for (int j = 0; j <= n; j++)
               if (s == -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j;
             Pivot(i, s);
           }
         }
         if (!Simplex(2)) return numeric_limits<DOUBLE>::infinity();
         x = VD(n);
         for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
         return D[m][n + 1];
       }
     };
typedef pll point;

long long ccw(point a, point b, point c) {
	b.first -= a.first; b.second -= a.second;
	c.first -= a.first; c.second -= a.second;
	return b.first * (long long)c.second - c.first * (long long)b.second;
}
#define fst first
#define snd second
pair<ld,pair<ld,ld> > getform(pll p, pll q) {
	ll px=p.fst,py=p.snd;
	ll qx=q.fst,qy=q.snd;
	ld a=py-qy;
	ld b=qx-px;
	ld c=px*qy-qx*py;
	return MP(a,MP(b,c));
}
pll vp[3];
ld go(ld t) {
	ld ct=cos(t);
	ld st=sin(t);
	VVD A;
	VD B;
	A.resize(6);
	B.resize(6);
	for (ll k=0;k<2;k++) {
		for (ll id=0;id<3;id++) {
			pair<ld,pair<ld,ld> > line = getform(vp[(id+1)%3],vp[id]);
			ld a=line.first,b=line.snd.fst,c=line.snd.snd;
			ld norm=sqrt(a*a+b*b);
			ll i=k*3+id;
			A[i].resize(3);
			A[i][0]=-a/norm;
			A[i][1]=-b/norm;
			A[i][2]=1;
			if (k) {
				A[i][2]=1-(2*(a*ct-b*st)/norm);
			}
			B[i]=c/norm;
		}
	}
	VD C; C.resize(3);
	C[2]=1;
	VD x;
  LPSolver solver(A, B, C);
  ld value = solver.Solve(x);
  return value;
}
const ll NUM=6000;
int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cout<<fixed<<setprecision(10);
	for (ll i=0;i<3;i++) {
		ll x,y; scanf("%lld%lld",&x,&y); vp[i]=MP(x,y);
	}
	if (ccw(vp[0],vp[1],vp[2])>0) reverse(vp,vp+3);
	assert(ccw(vp[0],vp[1],vp[2])<0);
	ld final=0;
	ld tick=M_PI/NUM;
	for (ll i=0;i<NUM;i++) {
		ld imin=tick*i,imax=tick*(i+1);
		for (ll j=0;j<40;j++) {
			ld imid=(imin+imax)/2;
			ld g0=go(imid),g1=go(imid+1e-11);
			chkmax(final,max(g0,g1));
			if (g0<g1) {
				imin=imid;
			}
			else imax=imid;
		}
	}
	cout<<final<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:170:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   ll x,y; scanf("%lld%lld",&x,&y); vp[i]=MP(x,y);
                                  ^

Judge Result