CSES - HIIT Open 2018 - Results
 Task: Euclidean Geometry Sender: barely div 2.8 burgeria Submission time: 2018-05-26 15:44:05 Language: C++ Status: READY Result: WRONG ANSWER
Test results
testverdicttime
#10.07 sdetails
#20.05 sdetails
#30.07 sdetails
#4--details
#50.06 sdetails
#60.06 sdetails
#70.07 sdetails
#80.07 sdetails

### Compiler report

```input/code.cpp: In function 'int limitChanges(std::vector<double>&, double)':
input/code.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); i++) {
~~^~~~~~~~~~
input/code.cpp: In function 'void asd(std::vector<std::__cxx11::basic_string<char> >&)':
input/code.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < mav.size(); i++) {
~~^~~~~~~~~~~~```

### Code

```#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long LL;

bool iszero(vector<string> & v, int row, int col) {
if (row < 0 || col < 0 || row >= 100 || col >= 100) return true;
return v[row][col] == '0';
}

bool isNb(int r1, int c1, int r2, int c2) {
if (abs(r2-r1) <= 1 && abs(c1-c2) <= 1) return true;
return false;
}
/*
vector<pair<int,int>> sorttaa(vector<pair<int,int>> & v) {
int row, int col;
row = v[0].first;
col = v[0].second;
vector<pair<int,int>> ans {{row, col}};
set<pair<int,int>> seen{{row, col}};
for (auto p : v) {
if (isNb(ans.back().first, ans.back().second, p.first, p.second) && seen.count(p) == 0) {
seen.insert(p);
ans.push_back(p);
}
}
return ans;

sort(v.begin(), v.end(), [](pair<int,int> left, pair<int,int> right) {
if (left.second != right.second) return left.second > right.second;
return left.first < right.first;
});
}
*/
pair<double, double> getavg(vector<pair<double, double>> & v, int idx) {
int sz = v.size();
double eka = 0;
double toka = 0;
double tot = 0;
for (int i = idx - 3; i < idx + 3; i++) {
int ac = (i + sz) % sz;
eka += v[ac].first;
toka += v[ac].second;
tot += 1;
}
eka /= tot;
toka /= tot;
double a = 0;
double b = 0;
for (int i = idx - 3; i < idx + 3; i++) {
int ac = (i + sz) % sz;
a += (v[ac].first - eka)*(v[ac].first - eka);
b += (v[ac].second - toka)*(v[ac].second - toka);
}
return {a,b};
}

int limitChanges(vector<double> & v, double limit) {
int limitChanges = 0;
for (int i = 1; i < v.size(); i++) {
if ((v[i] < limit) != (v[i-1] < limit)) {
limitChanges++;
}
}
if ((v[0] < limit) != (v.back() < limit)) limitChanges++;
return limitChanges;
}

bool isedge(vector<string> & v, int row, int col) {
vector<int> dr {1, -1, 0, 0};
vector<int> dc {0, 0, 1, -1};
for (int asd = 0; asd < 4; asd++) {
if (v[row][col] == '1' && iszero(v, row + dr[asd], col + dc[asd])) {
return true;
}
}
return false;

}

void asd(vector<string> & v) {
int row = 0; int col = 0;
for (; row < 100; row++) {
for (col=0; col < 100; col++) {
if (v[row][col] != '0') goto mansplaining;
}
}
mansplaining:

//cout << v[0][0] << " ";
//cout << row << "| " <<col <<endl;

vector<int> dr8 {-1, -1, 0, 1, 1, 1, 0, -1};
vector<int> dc8 {0, 1, 1, 1, 0, -1, -1, -1};
set<pair<int,int>> seen{{row, col}};
vector<pair<int,int>> ans{{row, col}};
while (true) {
bool brek = true;
for (int ff = 0; ff < 8; ff++) {
int candr = row + dr8[ff];
int candc = col + dc8[ff];
if (candr < 0 || candr >= 100 || candc < 0 || candc >= 100) continue;
//cout << row << " " << col << " " << candr << " " << candc << endl;
if (isedge(v, candr, candc) && !seen.count({candr, candc})) {
row = candr;
col = candc;
seen.emplace(row, col);
ans.emplace_back(row, col);
brek = false;
break;
}
}
if (brek) break;
}

vector<pair<double, double>> mav;
int sz = ans.size();
//cout << sz<<endl;
for (int i = 0; i < sz; i++) {
int end = (i + 7) % sz;
mav.emplace_back(ans[end].first - ans[i].first, ans[end].second - ans[i].second);
}

// moi jnalanko
vector<pair<double, double>> avg;

vector<double> tots;
for (int i = 0; i < mav.size(); i++) {
avg.emplace_back(getavg(mav, i));
tots.emplace_back(avg.back().first + avg.back().second);
}

double limit = 0.001;
int threes = 0;
int fours = 0;
//cout << tots.size() << endl;
//for (auto gg : tots) cout << gg << " ";
double inc = 0.001;
bool nonzeroseen = false;
while (true) {

int ls = limitChanges(tots, limit);
if (ls > 0) nonzeroseen = true;
//cout << ls << endl;
if (ls == 0 && nonzeroseen) break;
if (ls == 6) threes++;
if (ls == 8) fours++;
limit += inc;
inc *= 1.15;
}
//cout << threes << " " << fours << endl;
if (threes > fours) cout << 3;
else if (fours >= threes)cout << 4;
cout <<endl;
}

int main() {
/*
vector<pair<int,int>> test {{2,5},{1,5},{3,3}};
sorttaa(test);
for (auto a : test) cout << a.first << " " << a.second << endl;
return 0;
*/
int t; cin >> t;
while (t--) {
vector<string> v;
for (int i = 0; i < 100; i++) {
string s; cin>>s;
v.push_back(s);
}
asd(v);
}

}
```

### Test details

#### Test 1

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
3
3
3
3
4
...

#### Test 2

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
4
4
3
...

user output
3
4
4
4
3
...

#### Test 3

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
4
3
3
3
4
...

#### Test 4

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
4
3
...

user output
(empty)

#### Test 5

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
3
3
4
...

user output
3
4
3
3
4
...

#### Test 6

Verdict:

input
100
000000000000000000000000000000...

correct output
4
3
4
4
4
...

user output
4
3
4
4
3
...

#### Test 7

Verdict:

input
100
000000000000000000000000000000...

correct output
4
4
3
3
3
...

user output
4
4
3
3
3
...

#### Test 8

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
3
...

user output
4
3
3
3
3
...