제출 #196853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
196853		balbit	Fences (JOI18_fences)	C++14	100 / 100	21 ms	1144 KiB

fences

#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});
                  ^~

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49