제출 #670816

#제출 시각아이디문제언어결과실행 시간메모리
670816Antekb경계 (BOI14_demarcation)C++14
0 / 100
267 ms4084 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("trapv") #define st first #define nd second #define pb push_back #define eb emplace_back #define pp(x) pop_back(x) #define mp(a, b) make_pair(a, b) #define all(x) (x).begin(), (x).end() #define rev(x) reverse(all(x)) #define sor(x) sort(all(x)) #define sz(x) (int)(x).size() #define rsz(x) resize(x) using namespace std; ///~~~~~~~~~~~~~~~~~~~~~~~~~~ template <typename H, typename T> ostream& operator<<(ostream& os, pair<H, T> m){ return os <<"("<< m.st<<", "<<m.nd<<")"; } template <typename H> ostream& operator<<(ostream& os, vector<H> V){ os<<"{"; for(int i=0; i<V.size(); i++){ if(i)os<<" "; os<<V[i]; } os<<"}"; return os; } void debug(){cerr<<"\n";} template <typename H, typename... T> void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);} #define deb(x...) cerr<<#x<<" = ";debug(x); ///~~~~~~~~~~~~~~~~~~~~~~~~~ typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii > vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef string str; #define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int K=18, N=(1<<K), INF=1e9+5, mod=1e9+7, mod2=998244353; struct modint{ int n=0; modint(){} modint(ll x){ n=x%mod; if(n<0)n+=mod; } operator int(){ return n; } modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;} modint operator+=(modint a){return (*this)=(*this)+a;} modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;} modint operator-=(modint a){return (*this)=(*this)-a;} modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;} modint operator*=(modint a){return (*this)=(*this)*a;} modint operator^(const ll &m)const{ modint a(1); if(m==0)return a; if(m==1)return (*this); a=(*this)^(m/2); a*=a; return a*((*this)^(m&1)); } modint odw(){ return (*this)^((ll)mod-2); } modint operator/(modint a){return (*this)*a.odw();} modint operator/=(modint a){return (*this)=(*this)/a;} bool operator==(modint a){return a.n==n;} friend ostream& operator<<(ostream& os, modint m) { return os << m.n; } }; modint fact[N], fact2[N]; typedef vector<modint> vm; void factinit(){ fact[0]=1; for(int i=1; i<N; i++){ fact[i]=(fact[i-1]*modint(i))%mod; } fact2[N-1]=fact[N-1].odw(); for(int i=N-2; i>=0; i--){ fact2[i]=(fact2[i+1]*modint(i+1))%mod; } } modint npok(int _n, int _k){ return fact[_n]*fact2[_k]*fact2[_n-_k]; } void refx(vii &V){for(pii &i:V)i.nd=-i.nd;} void refy(vii &V){for(pii &i:V)i.st=-i.st;} void refxy(vii &V){for(pii &i:V)swap(i.st, i.nd);} bool cmp(vii &V, vii &V2){ int m1=0, m2=0; for(int i=0; i<V.size(); i++)if(V[i]<V[m1])m1=i; for(int i=0; i<V.size(); i++)if(V2[i]<V2[m2])m2=i; int x=V[m1].st-V2[m2].st, y=V[m1].nd-V2[m2].nd; for(int i=0;i<V.size(); i++){ if(V[m1].st-x!=V2[m2].st || V[m1].nd-y!=V2[m2].nd){ return 0; } if(++m1>=V.size())m1=0; if(++m2>=V.size())m2=0; } return 1; } bool row(vii &V, vii &V2){ //deb(V, V2); if(cmp(V, V2))return 1;refx(V); if(cmp(V, V2))return 1;refy(V); if(cmp(V, V2))return 1;refx(V); if(cmp(V, V2))return 1;refxy(V); //deb(V, V2); if(cmp(V, V2))return 1;refy(V); if(cmp(V, V2))return 1;refx(V); if(cmp(V, V2))return 1;refy(V); if(cmp(V, V2))return 1;refxy(V); rev(V); if(cmp(V, V2))return 1;refx(V); if(cmp(V, V2))return 1;refy(V); if(cmp(V, V2))return 1;refx(V); if(cmp(V, V2))return 1;refxy(V); //deb(V, V2); if(cmp(V, V2))return 1;refy(V); if(cmp(V, V2))return 1;refx(V); if(cmp(V, V2))return 1;refy(V); if(cmp(V, V2))return 1;refxy(V); //deb(V, V2); return 0; } pair<bool, pair<pii, pii>> solve(vii &V){ pair<bool, pair<pii, pii>> nie={0, {{0, 0}, {0, 0}}}; int n=V.size(); if(V[0].nd!=V[1].nd){ for(int i=0; i<n-1; i++)swap(V[i], V[i+1]); } ll A=0, A2=0; for(int i=0; i<n; i+=2){ A+=(V[i+1].st-V[i].st)*1ll*V[i].nd; deb((V[i+1].st-V[i].st)*1ll*V[i].nd); if(i<=n/2)A2+=(V[i+1].st-V[i].st)*1ll*V[i].nd; } if(A&1)return nie; A/=2; if(n&2){ for(int i=1; i<n; i+=2){ A2-=(V[i].st-V[i-1].st)*1ll*V[i].nd; int j=(i+n/2)%n; if((V[j].st-V[i].st)*1ll*(V[i].st-V[i-1].st)>0 && (A-A2)%(V[i].st-V[j].st)==0){ int h=(A-A2)/(V[i].st-V[j].st); if(h==V[i].nd){ deb(i); vector<pii> V2, V3; for(int k=i; k!=j; k=(k+1)%n){ V2.pb(V[k]); } V2.eb(V[j].st, h); V3.eb(V[j].st, h); for(int k=j; k!=i; k=(k+1)%n){ V3.pb(V[k]); } deb(V2, V3); if(row(V2, V3)){ bool b=1; for(int k=0; k<n; k+=2){ if(V[k].nd==h && min(max(V[k].st, V[k+1].st), max(V[i].st, V[j].st))> max(min(V[k].st, V[k+1].st), min(V[i].st, V[j].st)))b=0; if(min(V[i].st, V[j].st)<V[k+1].st && min(V[i].st, V[j].st) >V[k+1].st && min(V[k+1].nd, V[(k+2)%n].nd)<h && max(V[k+1].nd, V[(k+2)%n].nd)>h)b=0; } if(b)return {1, {V[i], {V[j].st, h}}}; } } } A2+=(V[j+1].st-V[j].st)*1ll*V[j].nd; } } else{ deb(A, A2); for(int i=1; i<n; i+=2){ A2-=(V[i].st-V[i-1].st)*1ll*V[i].nd; int j=(i+n/2)%n; deb(i, j, A2); if(V[i].st!=V[j].st && (A-A2)%(V[i].st-V[j].st)==0){ deb(i, j); int h=(A-A2)/(V[i].st-V[j].st); deb(h); if(h>=min(V[i].nd, V[(i+1)%n].nd) && h<=max(V[i].nd, V[(i+1)%n].nd) && h>=min(V[j].nd, V[(j+1)%n].nd) && h<=max(V[j].nd, V[(j+1)%n].nd)){ //deb(i); vector<pii> V2, V3; V2.pb({V[i].st, h}); if(V[(i+1)%n].nd!=h)V2.pb(V[(i+1)%n]); for(int k=(i+1)%n; k!=j%n; k=(k+1)%n){ if(k!=(i+1)%n)V2.pb(V[k]); } if(V[j].nd!=h)V2.pb(V[j]); V2.eb(V[j].st, h); V3.pb({V[j].st, h}); if(V[(j+1)%n].nd!=h)V3.pb(V[(j+1)%n]); for(int k=(j+1)%n; k!=i%n; k=(k+1)%n){ if(k!=(j+1)%n)V3.pb(V[k]); } if(V[i].nd!=h)V3.pb(V[i]); V3.eb(V[i].st, h); //deb(V2, V3); if(row(V2, V3)){ bool b=1; for(int k=0; k<n; k+=2){ if(V[k].nd==h && min(max(V[k].st, V[k+1].st), max(V[i].st, V[j].st))> max(min(V[k].st, V[k+1].st), min(V[i].st, V[j].st)))b=0; if(min(V[i].st, V[j].st)<V[k+1].st && min(V[i].st, V[j].st) >V[k+1].st && min(V[k+1].nd, V[(k+2)%n].nd)<h && max(V[k+1].nd, V[(k+2)%n].nd)>h)b=0; } if(b)return {1, {{V[i].st, h}, {V[j].st, h}}}; } } } A2+=(V[(j+2)%n].st-V[(j+1)%n].st)*1ll*V[(j+1)%n].nd; } } return nie; } int main(){ //factinit(); //BOOST; int n; cin>>n; vii V(n); for(auto &i:V)cin>>i.st>>i.nd;//, i.st*=2, i.nd*=2; auto t=solve(V); //return 0; deb("a", t.st); if(t.st==0){ refxy(V); t=solve(V); swap(t.nd.st.st, t.nd.st.nd); swap(t.nd.nd.st, t.nd.nd.nd); } deb("a", t.st); if(t.st==0){ refxy(V); rev(V); t=solve(V); } deb("a", t.st); if(t.st==0){ refxy(V); t=solve(V); swap(t.nd.st.st, t.nd.st.nd); swap(t.nd.nd.st, t.nd.nd.nd); } if(t.st==0)cout<<"NO\n"; else{ //cout<<ld(t.nd.st.st)/2<<" "<<ld(t.nd.st.nd)/2<<" "<<ld(t.nd.nd.st)/2<<" "<<ld(t.nd.nd.nd)/2; cout<<t.nd.st.st<<" "<<t.nd.st.nd<<" "<<t.nd.nd.st<<" "<<t.nd.nd.nd; } }

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

demarcation.cpp: In function 'bool cmp(vii&, vii&)':
demarcation.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for(int i=0; i<V.size(); i++)if(V[i]<V[m1])m1=i;
      |               ~^~~~~~~~~
demarcation.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0; i<V.size(); i++)if(V2[i]<V2[m2])m2=i;
      |               ~^~~~~~~~~
demarcation.cpp:117:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i=0;i<V.size(); i++){
      |              ~^~~~~~~~~
demarcation.cpp:121:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   if(++m1>=V.size())m1=0;
      |      ~~~~^~~~~~~~~~
demarcation.cpp:122:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   if(++m2>=V.size())m2=0;
      |      ~~~~^~~~~~~~~~
demarcation.cpp: In function 'bool row(vii&, vii&)':
demarcation.cpp:128:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  128 |  if(cmp(V, V2))return 1;refx(V);
      |  ^~
demarcation.cpp:128:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  128 |  if(cmp(V, V2))return 1;refx(V);
      |                         ^~~~
demarcation.cpp:129:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  129 |  if(cmp(V, V2))return 1;refy(V);
      |  ^~
demarcation.cpp:129:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  129 |  if(cmp(V, V2))return 1;refy(V);
      |                         ^~~~
demarcation.cpp:130:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  130 |  if(cmp(V, V2))return 1;refx(V);
      |  ^~
demarcation.cpp:130:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  130 |  if(cmp(V, V2))return 1;refx(V);
      |                         ^~~~
demarcation.cpp:131:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  131 |  if(cmp(V, V2))return 1;refxy(V);
      |  ^~
demarcation.cpp:131:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  131 |  if(cmp(V, V2))return 1;refxy(V);
      |                         ^~~~~
demarcation.cpp:133:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  133 |  if(cmp(V, V2))return 1;refy(V);
      |  ^~
demarcation.cpp:133:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  133 |  if(cmp(V, V2))return 1;refy(V);
      |                         ^~~~
demarcation.cpp:134:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  134 |  if(cmp(V, V2))return 1;refx(V);
      |  ^~
demarcation.cpp:134:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  134 |  if(cmp(V, V2))return 1;refx(V);
      |                         ^~~~
demarcation.cpp:135:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  135 |  if(cmp(V, V2))return 1;refy(V);
      |  ^~
demarcation.cpp:135:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  135 |  if(cmp(V, V2))return 1;refy(V);
      |                         ^~~~
demarcation.cpp:136:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  136 |  if(cmp(V, V2))return 1;refxy(V);
      |  ^~
demarcation.cpp:136:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  136 |  if(cmp(V, V2))return 1;refxy(V);
      |                         ^~~~~
demarcation.cpp:138:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  138 |  if(cmp(V, V2))return 1;refx(V);
      |  ^~
demarcation.cpp:138:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  138 |  if(cmp(V, V2))return 1;refx(V);
      |                         ^~~~
demarcation.cpp:139:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  139 |  if(cmp(V, V2))return 1;refy(V);
      |  ^~
demarcation.cpp:139:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  139 |  if(cmp(V, V2))return 1;refy(V);
      |                         ^~~~
demarcation.cpp:140:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  140 |  if(cmp(V, V2))return 1;refx(V);
      |  ^~
demarcation.cpp:140:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  140 |  if(cmp(V, V2))return 1;refx(V);
      |                         ^~~~
demarcation.cpp:141:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  141 |  if(cmp(V, V2))return 1;refxy(V);
      |  ^~
demarcation.cpp:141:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  141 |  if(cmp(V, V2))return 1;refxy(V);
      |                         ^~~~~
demarcation.cpp:143:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  143 |  if(cmp(V, V2))return 1;refy(V);
      |  ^~
demarcation.cpp:143:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  143 |  if(cmp(V, V2))return 1;refy(V);
      |                         ^~~~
demarcation.cpp:144:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  144 |  if(cmp(V, V2))return 1;refx(V);
      |  ^~
demarcation.cpp:144:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  144 |  if(cmp(V, V2))return 1;refx(V);
      |                         ^~~~
demarcation.cpp:145:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  145 |  if(cmp(V, V2))return 1;refy(V);
      |  ^~
demarcation.cpp:145:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  145 |  if(cmp(V, V2))return 1;refy(V);
      |                         ^~~~
demarcation.cpp:146:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  146 |  if(cmp(V, V2))return 1;refxy(V);
      |  ^~
demarcation.cpp:146:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  146 |  if(cmp(V, V2))return 1;refxy(V);
      |                         ^~~~~
demarcation.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with H = std::pair<int, int>; std::ostream = std::basic_ostream<char>]':
demarcation.cpp:39:30:   required from 'void debug(H, T ...) [with H = std::vector<std::pair<int, int> >; T = {std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >}]'
demarcation.cpp:182:6:   required from here
demarcation.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...