Submission #78696

#TimeUsernameProblemLanguageResultExecution timeMemory
78696dualityThe Forest of Fangorn (CEOI14_fangorn)C++11
100 / 100
298 ms1548 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #define x first #define y second const double PI = acos(-1.0); int cx[10000],cy[10000]; int tx[2000],ty[2000]; pii a[2000],b[2000]; double diff(double a,double b) { return (a > b) ? a-b:a-b+2*PI; } int ccw(pii a,pii b,pii c) { return (LLI) (b.x-a.x)*(c.y-b.y) > (LLI) (b.y-a.y)*(c.x-b.x); } vi ans; int main() { int i; int C,N; int gx,gy; scanf("%*d %*d %d %d %d",&gx,&gy,&C); for (i = 0; i < C; i++) scanf("%d %d",&cx[i],&cy[i]); scanf("%d",&N); for (i = 0; i < N; i++) scanf("%d %d",&tx[i],&ty[i]); int j; for (i = 0; i < N; i++) { pair<double,pii> ca = mp(1e99,mp(0,0)),cb; double angle = atan2(ty[i]-gy,tx[i]-gx); for (j = 0; j < N; j++) { if (i != j) { pair<double,pii> t = mp(atan2(ty[j]-ty[i],tx[j]-tx[i]),mp(tx[j],ty[j])); if (ca.first == 1e99) ca = cb = t; else { if (diff(angle,t.first) < diff(angle,ca.first)) ca = t; if (diff(t.first,angle) < diff(cb.first,angle)) cb = t; } } } a[i] = ca.second,b[i] = cb.second; } for (i = 0; i < C; i++) { for (j = 0; j < N; j++) { pii p = mp(2*tx[j]-cx[i],2*ty[j]-cy[i]); if (ccw(a[j],mp(tx[j],ty[j]),b[j])) { if (ccw(mp(tx[j],ty[j]),b[j],p) && ccw(mp(tx[j],ty[j]),p,a[j])) break; } else { if (!ccw(mp(tx[j],ty[j]),a[j],p) || !ccw(mp(tx[j],ty[j]),p,b[j])) break; } } if (j >= N) ans.pb(i); } printf("%d\n",ans.size()); for (i = 0; i < ans.size(); i++) printf("%d%c",ans[i]+1,(i == ans.size()-1) ? '\n':' '); return 0; }

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:108:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",ans.size());
                   ~~~~~~~~~~^
fangorn.cpp:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < ans.size(); i++) printf("%d%c",ans[i]+1,(i == ans.size()-1) ? '\n':' ');
                 ~~^~~~~~~~~~~~
fangorn.cpp:109:64: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < ans.size(); i++) printf("%d%c",ans[i]+1,(i == ans.size()-1) ? '\n':' ');
                                                              ~~^~~~~~~~~~~~~~~
fangorn.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*d %*d %d %d %d",&gx,&gy,&C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:76:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < C; i++) scanf("%d %d",&cx[i],&cy[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
fangorn.cpp:78:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d %d",&tx[i],&ty[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...