CSES - HIIT Open 2018 - Results
 Task: Euclidean Geometry Sender: Ukkonen Fan Club Submission time: 2018-05-26 14:29:26 +0300 Language: C++ Status: READY Result: WRONG ANSWER
Test results
testverdicttime
#10.03 sdetails
#20.04 sdetails
#30.03 sdetails
#40.04 sdetails
#50.04 sdetails
#60.03 sdetails
#70.04 sdetails
#80.03 sdetails

### Code

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

int D2=300;
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);
}

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))>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});
}
}
if (d2(dh[0], uh[0])<D2) dh[0]=uh[0]=md(dh[0], uh[0]);
if (d2(dh[dh.size()-1], uh[uh.size()-1])<D2) 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())<D2) 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())<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])) ++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]) ) ++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 details

#### Test 1

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
3
4
3
3
5
...
Truncated

#### Test 2

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
4
4
3
...

user output
3
4
4
5
4
...
Truncated

#### Test 3

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
4
3
3
3
4
...
Truncated

#### Test 4

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
4
3
...

user output
3
5
3
5
3
...
Truncated

#### Test 5

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
3
3
4
...

user output
3
4
4
4
5
...
Truncated

#### Test 6

Verdict:

input
100
000000000000000000000000000000...

correct output
4
3
4
4
4
...

user output
5
4
6
4
4
...
Truncated

#### Test 7

Verdict:

input
100
000000000000000000000000000000...

correct output
4
4
3
3
3
...

user output
5
4
4
4
4
...
Truncated

#### Test 8

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
3
...

user output
3
4
3
3
3
...
Truncated