제출 #196853

#제출 시각아이디문제언어결과실행 시간메모리
196853balbitFences (JOI18_fences)C++14
100 / 100
21 ms1144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define ull unsigned ll #define f first #define s second #define FOR(i,a,b) for (int i=(a); i<(b); ++i) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) for (int i=(n-1); i>=0; --i) #define REP1(i,n) FOR(i,1,n+1) #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() #define SQ(x) (x)*(x) #define MN(a,b) a = min(a,(__typeof__(a))(b)) #define MX(a,b) a = max(a,(__typeof__(a))(b)) #define pb push_back #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #ifdef BALBIT #define IOS() #define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__); template<typename T> void _do(T &&x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);} #else #define IOS() ios_base::sync_with_stdio(0);cin.tie(0); #define endl '\n' #define bug(...) #endif const int iinf = 1<<29; const ll inf = 1ll<<60; const ll mod = 1e9+7; void GG(){cout<<"-1\n"; exit(0);} ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod ll re=1; while (n>0){ if (n&1) re = re*a %mo; a = a*a %mo; n>>=1; } return re; } ll inv (ll b, ll mo = mod){ if (b==1) return b; return (mo-mo/b) * inv(mo%b) % mo; } const int maxn = 1e5+5; struct pt{ double x, y; bool operator < (const pt &b) const { return tie(x,y) < tie(b.x,b.y); } pt operator + (const pt &b) const { return {x+b.x,y+b.y}; } pt operator - (const pt &b) const { return {x-b.x,y-b.y}; } pt operator * (const double d) const { return {x*d,y*d}; } pt operator / (const double d) const { return {x/d,y/d}; } double operator * (const pt &b) const { return x*b.x + y*b.y; } double operator ^ (const pt &b) const { // Cross! return x*b.y - y*b.x; } double len() { return hypot(x,y); } pt(double xx=0, double yy=0): x(xx), y(yy){ } }; struct line{ pt a, b, ab; // start and end points line(pt _a, pt _b) { a=_a; b=_b; ab = b-a; } double len(){ ab = b-a; return ab.len(); } line(){} }; double dist(pt &a, pt &b) { return hypot(a.x-b.x,a.y-b.y); } pt proj(line p, pt q) { // Point of minimum projection if (p.ab.len() == 0) return p.a; double k = (q-p.a)*(p.ab)/(SQ(p.ab.x) + SQ(p.ab.y)); // scaled factor of p if (k<=0) return p.a; // on left if (k >= 1) return p.b; // on right return p.a + p.ab * k; } const double eps = 1e-7; line wall[5]; const int MX = 4*200 + 8 + 10; double d[MX][MX][2]; // Id 1, Id 2, parity line fen[MX]; bool its(line p, line q) { return ((q.a-p.a) ^ p.ab) * ((q.b-p.a) ^ p.ab) < 0 && ((p.a-q.a) ^ q.ab) * ((p.b-q.a) ^ q.ab) < 0; // If the ends of q are on different sides (opposite cross signs of p) and same applies for p // Strictly less: touching is acceptable in case fence goes along the wall } bool ok(line p) { REP(i,5) if (its(p,wall[i])) return 0; return 1; } double dinf = 1e10; line CUT = {{0,0},{1,7*11*13}}; signed main(){ IOS(); int n, s; cin>>n>>s; // Build the walls wall[0] = {{-s,s},{s,s}}; wall[1] = {{s,s},{s,-s}}; wall[2] = {{s,-s},{-s,-s}}; wall[3] = {{-s,-s},{-s,s}}; wall[4] = {{0,s},{0,-s}}; // To prevent diagonals of the square from skipping to each other REP(i,n) { int a, b, c, d; cin>>a>>b>>c>>d; fen[i] = {{a,b},{c,d}}; } REP(i,4) { fen[i+n] = {wall[i].a,wall[i].a}; // Dummy lines for corners } bug((proj(fen[2],fen[3].a)-fen[3].a).len()); n+=4; REP(i,n) REP(j,n) REP(k,2){ if (i==j && k==0) d[i][j][k] = 0; else { bool IJ = its(CUT,{fen[i].a, fen[j].a}); bool B; // Assume the person is sitting at a for each fence d[i][j][0]=d[i][j][1]=1e10; line to; // bug(d[i][j][B]); to = {fen[i].a,proj(fen[j],fen[i].a)}; B = its(CUT,to) ^ its(CUT,line(fen[j].a,to.b)); if (ok(to)) MN(d[i][j][B],to.len() ); // First project from fen[i].a to fen[j], then walk back to fen[j].a to = {fen[i].b,proj(fen[j],fen[i].b)}; B = its(CUT,to)^its(CUT,fen[i])^its(CUT,line(fen[j].a,to.b)); if (ok(to)) MN(d[i][j][B],to.len()); to = {fen[j].a,proj(fen[i],fen[j].a)}; B = its(CUT,to)^its(CUT,line(fen[i].a,to.b)); if (ok(to)) MN(d[i][j][B],to.len() ); to = {fen[j].b,proj(fen[i],fen[j].b)}; B = its(CUT,to)^its(CUT,fen[j])^its(CUT,line(fen[i].a,to.b)); if (ok(to)) MN(d[i][j][B],to.len() ); MN(d[j][i][0], d[i][j][0]); // It's the same going backwards MN(d[j][i][1], d[i][j][1]); bug(i,j,d[i][j][0],d[i][j][1]); } } REP(k,n) REP(i,n) REP(j,n) REP(b1,2) REP(b2,2){ MN(d[i][j][b1^b2],d[i][k][b1] + d[k][j][b2]); // Floyd Warshall } bug("NOEFNOW"); double re = 1e10; REP(i,n) REP(j,n) REP(k,2){ MN(re, d[i][i][1]); bug(i,j,k,d[i][j][k]); } cout<<re<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

fences.cpp: In function 'int main()':
fences.cpp:137:17: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[0] = {{-s,s},{s,s}};
                 ^
fences.cpp:137:28: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[0] = {{-s,s},{s,s}};
                            ^
fences.cpp:137:28: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
fences.cpp:137:28: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
fences.cpp:138:28: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[1] = {{s,s},{s,-s}};
                            ^
fences.cpp:138:28: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
fences.cpp:138:28: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
fences.cpp:138:25: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[1] = {{s,s},{s,-s}};
                         ^
fences.cpp:139:30: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[2] = {{s,-s},{-s,-s}};
                              ^
fences.cpp:139:19: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[2] = {{s,-s},{-s,-s}};
                   ^
fences.cpp:139:24: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[2] = {{s,-s},{-s,-s}};
                        ^
fences.cpp:139:27: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[2] = {{s,-s},{-s,-s}};
                           ^
fences.cpp:140:17: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[3] = {{-s,-s},{-s,s}};
                 ^
fences.cpp:140:20: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[3] = {{-s,-s},{-s,s}};
                    ^
fences.cpp:140:25: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[3] = {{-s,-s},{-s,s}};
                         ^
fences.cpp:140:30: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[3] = {{-s,-s},{-s,s}};
                              ^
fences.cpp:141:28: warning: narrowing conversion of 'second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[4] = {{0,s},{0,-s}}; // To prevent diagonals of the  square from skipping to each other
                            ^
fences.cpp:141:25: warning: narrowing conversion of '- second' from 'int' to 'double' inside { } [-Wnarrowing]
     wall[4] = {{0,s},{0,-s}}; // To prevent diagonals of the  square from skipping to each other
                         ^
fences.cpp:144:30: warning: narrowing conversion of 'a' from 'int' to 'double' inside { } [-Wnarrowing]
         fen[i] = {{a,b},{c,d}};
                              ^
fences.cpp:144:30: warning: narrowing conversion of 'b' from 'int' to 'double' inside { } [-Wnarrowing]
fences.cpp:144:30: warning: narrowing conversion of 'c' from 'int' to 'double' inside { } [-Wnarrowing]
fences.cpp:144:30: warning: narrowing conversion of 'd' from 'int' to 'double' inside { } [-Wnarrowing]
fences.cpp:157:18: warning: unused variable 'IJ' [-Wunused-variable]
             bool IJ = its(CUT,{fen[i].a, fen[j].a});
                  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...