Euclidean Geometry

#include <bits/stdc++.h>
#define x real()
#define Y imag()
#define F first
#define S second
const double SIDE_THRESHOLD = 5;
 
int D2=350;
double MA=20.0   /180.0*3.14159265358979;
 
 
using namespace std;
char t[111][111];
typedef long long ll;
typedef complex<double> co;
 
 
long long d2(pair<int, int> a, pair<int, int> b){
    return (a.F-b.F)*(a.F-b.F)+(a.S-b.S)*(a.S-b.S);
}
 
 
double dotP(pair<int, int> a, pair<int, int> b){
    return a.F*b.F+a.S*b.S;
}
 
 
double angle(pair<int, int> a, pair<int, int> b){
    return acos(dotP(a,b)/sqrt(dotP(a,a)*dotP(b,b)));
}
 
bool ok(pair<int, int> a, pair<int, int> b, pair<int, int> c){
    pair<int, int> v1={b.F-a.F, b.S-a.S};
    pair<int, int> v2={c.F-b.F, c.S-b.S};
    return abs(angle(v1, v2))>MA;
}
 
void solve(){
    int n=100;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin>>t[i][j];
        }
    }
    vector<pair<int, int> > dh;
    vector<pair<int, int> > uh;
    for (int i=0;i<n;++i){
        bool f=0;
        int l=0;
        for (int j=0;j<n;++j){
            if (t[i][j]=='1'){
                if (!f) uh.push_back({i,j});
                f=1;
                l=j;
            }
        }
        if (f){
            dh.push_back({i,l});
        }
    }
    vector<pair<int, int> > dsh;
    vector<pair<int, int> > ush;
    dsh.push_back(dh[0]);
    ush.push_back(uh[0]);
    for (auto v:dh){
        if (dsh.size()==1){
            if (d2(v, dsh.back())<D2/4) continue;
            dsh.push_back(v);
        }else{
            if (!ok(dsh[dsh.size()-2], dsh[dsh.size()-1], v)) dsh.pop_back();
            if (d2(v, dsh.back())<D2) continue;
            dsh.push_back(v);
        }
    }
    for (auto v:uh){
        if (ush.size()==1){
            if (d2(v, ush.back())<D2/4) continue;
            ush.push_back(v);
        }else{
            if (!ok(ush[ush.size()-2], ush[ush.size()-1], v)) ush.pop_back();
            if (d2(v, ush.back())<D2) continue;
            ush.push_back(v);
        }
    }
    int minus=0;
    if (dsh[0]!=ush[0]){
        if (!ok(dsh[0], ush[0], ush[1]) || !ok(ush[0], dsh[0], dsh[1]) || d2(ush[0], dsh[0])<D2/4) ++minus;
    }
    if (dsh.back()!=ush.back()){
        if (!ok(dsh.back(), ush.back(), ush[ush.size()-2]) || !ok(ush.back(), dsh.back(), dsh[dsh.size()-2])  || d2(ush.back(), dsh.back())<D2/4) ++minus;
    }
    set<pair<int, int> > k;
    for (auto v:dsh) k.insert(v);
    for (auto v:ush) k.insert(v);
//     for (auto n:k) cout << n.F << ", " << n.S << endl;
    cout << k.size()-minus << "\n";
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t;
    cin >> t;
    for (int i=0;i<t;++i)solve();
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED