oToToT的code收藏區

題目連結: https://codeforces.com/problemset/problem/1017/E 比賽unrated了，不知道好險還是好慘，前面做題真的做超慢，然後到現在還是不知道為什麼C那樣做就好了。 不過這題其實滿有趣的。 可以發現這題其實要問的就是兩個東東他們的凸包是否相同(允許旋轉及位移，但不能鏡射)，原因就是會發現結束的時候，一個engine構成的power field一定會變成一個凸多邊形，然後現在考慮若是拆掉凸多邊形上任意一個頂點，那他必定會縮進去(沒有兩個點在相同的位置)，所以我們一定要用另外一個engine來補，才可以讓他不會縮進去，也因此其實就是每個頂點都要在一樣的位置。 那要怎麼做呢？當然，先求出凸包之後，拿到的凸包顯然會按(順/逆)(看實作)時鐘的方式排序點，所以我們其實就是要求，兩個凸包是否有某種旋轉操作(abc->bca->cab...)使他們相同。 我原先是用booth's algorithm幫兩個東東都求出最小字典序的旋轉，再來一個一個比較是否一樣，但也有其他作法。 字串相關的作法就是將其中一個凸包複製一次貼在自己後面(abc->abcabc)，然後hash或kmp直接求是否另一個凸包出現在裡面。 不過其實暴力枚舉一個東東旋轉後的長相然後判斷相等就可以過了，因為其實整數點上的凸包大小最多只有$\sqrt{C}$，所以直接枚舉的複雜度也才$\sqrt{C} \times \sqrt{C} = C$。 但這題最難的點，我覺得其實要怎麼把凸包變成一個序列，且他可以拿來判斷旋轉位移後可以一樣，但鏡射不行，原本我的想法只有判斷所有邊的長度跟所有角的角度是否一樣，但是卻被 Hack 掉了，後來才發現我需要把角跟邊擺在一起才可以成立，不然鏡射的話他拿的邊順序及角順序也可以一樣，但實際卻長得不一樣。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) begin(x), end(x) #define SZ(x) (static_cast<int>((x).size())) using lld = int64_t; ...

題目連結: http://tioj.infor.org/problems/1280 應該很明顯就是要求個凸包的面積，那就先求個凸包，求法就是先求出上凸包，再求下凸包，看上下凸包的方法也不難，就看看兩個相鄰的邊的夾角是不是超過180度就好。接著要求面積就直接算個有向面積加起來，而因為剛剛求凸包的順序關西，我們求有向面積的時候甚至不需要極角排序，直接求就好了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 10000 + 5; inline PLL operator-(const PLL &a, const PLL &b){ return {a.FF-b.FF, a.SS-b.SS}; } inline lld cross(const PLL &a, const PLL &b){ return a.FF*b.SS - b.FF*a.SS; } inline lld cross(const PLL &o, const PLL &a, const PLL &b){ return cross(a-o, b-o); } PLL arr[N]; vector<PLL> hull1, hull2; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i].FF>>arr[i].SS; sort(arr, arr+n); for(int i=0;i<n;i++){ w...

題目連結: http://tioj.infor.org/problems/1559 數學不好，想了一下下。我的作法是求出給定兩個點的距離跟夾角，之後以其中一個點為暫時原點，然後用極座標轉回普通座標方式的作法找到60度的點，再平移回剛剛的暫時原點即可。 #include <bits/stdc++.h> using namespace std; typedef pair<double,double> PDD; #define X first #define Y second #define deg2rad(x) (acos(-1)*x/180.) int main(){ PDD a,b, ans1, ans2; while(cin>>a.X>>a.Y>>b.X>>b.Y){ double dis = sqrt((a.X-b.X)*(a.X-b.X)+(a.Y-b.Y)*(a.Y-b.Y)); double theta = atan2((b.Y-a.Y), (b.X-a.X)); ans1 = {a.X+dis*cos(deg2rad(60)+theta), a.Y+dis*sin(deg2rad(60)+theta)}; ans2 = {a.X+dis*cos(deg2rad(300)+theta), a.Y+dis*sin(deg2rad(300)+theta)}; if(ans2<ans1) swap(ans1,ans2); cout<<setprecision(3)<<fixed<<ans1.X<<' '<<ans1.Y<<' '<<ans2.X<<' '<<ans2.Y<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1105 如果我沒猜錯的話，這題應該可以用旋轉卡尺做到$O(n log n)$，但是我實在不熟，加上本題範圍$O(n^2)$就可以過了，所以我就直接寫個裸裸的做法了 #include <bits/stdc++.h> using namespace std; #define N 3000 typedef pair<int,int> PII; #define X first #define Y second #define DIS(a,b) ((arr[a].X-arr[b].X)*(arr[a].X-arr[b].X)+(arr[a].Y-arr[b].Y)*(arr[a].Y-arr[b].Y)) PII arr[N+5]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; while(n>0){ int a=0, b=0; for(int i=0;i<n;i++) cin>>arr[i].X>>arr[i].Y; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(DIS(a,b) < DIS(i, j)) a=i, b=j; cout<<a<<' '<<b<<'\n'; cin>>n; } return 0; }

題目連結: http://tioj.infor.org/problems/1115 計算幾何題OAO，我三角函數有點爛ww，不過大概就是y>0時，就是算整個原扣掉在下面那塊，也就是扇形減三角形，而y #include <bits/stdc++.h> using namespace std; const double PI = acos(-1); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); double x,y,r,ans; while(cin>>x>>y>>r){ double theta = acos(abs(y/r))*2; if(y>=r) ans=r*r*PI; else if(y<=-r) ans=0; else if(y<=0) ans = r*r*theta/2. - r*r*sin(theta)/2.; else ans = r*r*PI - r*r*theta/2. + r*r*sin(theta)/2.; cout<<fixed<<setprecision(2)<<ans<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1371 裸的凸包，由左至右掃過去維護上凸包跟下凸包，維護方法就是看加入當前這個點是不是在前面兩個所連線的上方(上凸包的話)，如果是就把前一個砍掉，不然就塞進去，下凸包也同理。 不過本題要注意相同高度的點就不用輸出了 #include <bits/stdc++.h> using namespace std; typedef long long lld; struct point{ lld x,y; int id; point(){} point(lld a,lld b,lld c){x=a;y=b;id=c;} point(lld a,lld b){x=a;y=b;} }; inline lld cross(const point& a,const point& b){ return a.x*b.y-a.y*b.x; } vector<point> dots; vector<point> cHull; vector<point> ans; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=1;i<=n;i++){ lld a,b;cin>>a>>b; dots.push_back(point(a,b,i)); } sort(dots.begin(),dots.end(),[](const point& a,const point& b){return (a.x!=b.x)?(a.x<b.x):(a.y<b.y);}); for(int i=0;i<dots.size();i++){ while(cHul...

題目連結: http://tioj.infor.org/problems/1178 裸裸的凸包題，不過凸包該如何做呢?可以用掃描線的概念，從左至右掃一遍，試試看某個點會不會是凸包的一部分，試驗方法就是看這個點與相鄰且在暫時凸包的兩個點的夾角，如果大於180則中間那個點將不會是凸包的一部分(可用外積判斷是否大於180)，這樣可求出上凸包，從右至左再掃一遍就可以找到下凸包了XD #include <bits/stdc++.h> using namespace std; typedef long long lld; struct point{ lld x,y; point(lld a,lld b){x=a;y=b;} }; inline lld cross(point a, point b){ return a.x*b.y-a.y*b.x; } vector<point> dots; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,ans=0;cin>>n; for(int i=0;i<n;i++){ lld a,b;cin>>a>>b; dots.push_back(point(a,b)); } vector<point> cHull; sort(dots.begin(), dots.end(), [](const point& a, const point& b){return a.x<b.x;}); for(auto i:dots){ while(cHull.size()>=2){ int sz=cHull.size()-1; if(cross(point(cHull[sz].x-cHull[sz-1].x,cHull[sz]....