Euclidean Geometry

#include <bits/stdc++.h>
#define x real()
#define Y imag()
#define F first
#define S second
const double SIDE_THRESHOLD = 5;


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);
}

pair<int, int> md(pair<int, int> a, pair<int, int> b){
    return {(a.F+b.F)/2, (a.S+b.S)/2};
}

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))>0.7;
}

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});
        }
    }
    if (d2(dh[0], uh[0])<350) dh[0]=uh[0]=md(dh[0], uh[0]);
    if (d2(dh[dh.size()-1], uh[uh.size()-1])<350) dh[dh.size()-1]=uh[uh.size()-1]=md(dh[dh.size()-1], uh[uh.size()-1]);
    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) dsh.push_back(v);
        else{
            if (!ok(dsh[dsh.size()-2], dsh[dsh.size()-1], v)) dsh.pop_back();
            if (d2(v, dsh.back())<350) continue;
            dsh.push_back(v);
        }
    }
    for (auto v:uh){
        if (ush.size()==1) ush.push_back(v);
        else{
            if (!ok(ush[ush.size()-2], ush[ush.size()-1], v)) ush.pop_back();
            if (d2(v, ush.back())<350) continue;
            ush.push_back(v);
        }
    }
    int minus=0;
    if (dsh[0]!=ush[0]){
        if (!ok(ush[0], dsh[0], ush[1]) || !ok(ush[0], dsh[0], dsh[1])) ++minus;
    }
    if (dsh.back()!=ush.back()){
        if (!ok(ush.back(), dsh.back(), ush[ush.size()-2]) || !ok(ush.back(), dsh.back(), dsh[dsh.size()-2]) ) ++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: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER