#include <unordered_set>
#include "arithmetics.h"
#include <iostream>
#include <vector>
#include <climits>
#include <set>
using namespace std;
pair<long long, long long> calcWaysRook(pair<long long, long long> start, pair<long long, long long> end)
{
if(start.second == end.second)
{
return {1,1};
}
else
{
return {2,2};
}
}
bool reachableForQueenInOneMove(pair<long long, long long> start, pair<long long, long long> end, long long numRows, long long numCols)
{
if(start.first > numRows || start.second > numCols || start.first <= 0 ||start.second <= 0)
return false;
return start.second == end.second ||( abs(start.second - end.second) == end.first-start.first);
}
class Punkt
{public:
long long x; long long y;
Punkt()
{
};
Punkt(int xn, int yn)
:x(xn), y(yn)
{
};
bool operator!=(const Punkt& other)
{
return !(other.x == x && other.y == y);
}
bool operator==(const Punkt& other)
{
return other.x == x && other.y == y;
}
bool operator<(const Punkt& other)
{
if(x<other.x)
return true;
else
return y < other.y;
}
};
class Gerade
{
public:
long long m, b;
Punkt p1, p2;
Gerade(Punkt pt1, Punkt pt2)
:
p1(pt1),
p2(pt2)
{
if(( pt2.x - pt1.x) ==0)
{
m = INT_MAX;
b = pt2.x;
}
else
{
m = (pt2.y -pt1.y) /( pt2.x - pt1.x);
b = pt2.y - m*pt2.x;
}
}
long long f(long long x)
{
return m*x +b;
}
Punkt intersection(const Gerade& other)
{
long long zaehler = other.b - b;
long long nenner = m - other.m;
if(m == INT_MAX)
{
if(other.m == INT_MAX)
return Punkt(-1,-1);
else
return Punkt(b, other.m+b + other.b);
}
if(other.m == INT_MAX)
{
return Punkt(other.b, m*other.b + b);
}
if(nenner == 0)
return Punkt(-1,-1);
if(zaehler % nenner == 0)
{
return Punkt(zaehler / nenner, f(zaehler/nenner));
}
else
{
return {-1,-1};
}
}
};
vector<Gerade> generateLinesQueen(Punkt start)
{
vector<Gerade> v;
v.push_back(Gerade(start, Punkt(start.x+1, start.y-1)));
v.push_back(Gerade(start, Punkt(start.x-1, start.y)));
v.push_back(Gerade(start, Punkt(start.x-1, start.y-1)));
v.push_back(Gerade(start, Punkt(start.x+1, start.y)));
v.push_back(Gerade(start, Punkt(start.x, start.y-1)));
return v;
}
vector<Punkt> getIntersections(vector<Gerade> v1, vector<Gerade> v2)
{
vector<pair<long long, long long>> v;
for(auto g : v1)
{
for(auto f:v2)
{
Punkt inter = g.intersection(f);
if(inter != Punkt(-1,-1))
v.push_back({inter.x, inter.y});
}
}
set<pair<long long, long long>> s(v.begin(), v.end());
vector<Punkt> vf;
for(auto it : s)
vf.push_back(Punkt(it.first, it.second));
return vf;
}
long long numQueenWays(Punkt start, Punkt end, long long numR, long long numC)
{
start = Punkt(start.y, start.x);
end = Punkt(end.y, end.x);
long long res = 0;
vector<Gerade> gStart = generateLinesQueen(start);
vector<Gerade> gEnd = generateLinesQueen(end);
vector<Punkt> intersections = getIntersections(gStart, gEnd);
for(auto p : intersections)
{
if(p.x > 0 && p.x <= numC && p.y > 0 && p.y <= numR)
res++;
}
for(auto p : intersections)
{
if(p == start || p == end)
return -2;
}
return res;
}
/*
pair<long long, long long> calcWaysQueen(long long numR, long long numC, pair<long long, long long> start, pair<long long, long long> end)
{
if(start.second == end.second || (abs(start.second - end.second) == end.first-start.first))
{
return {1,1};
}
else
{
int numPaths = 4;
//try all directions
//straight to other side then diagonal /diagonal the nstraight
if(start.second < end.second)
{
long long wantStartCol = end.second - (end.first - start.first);
if(reachableForQueenInOneMove({start.first, wantStartCol}, end, numR, numC))
numPaths++;
if(reachableForQueenInOneMove(start, {end.first, end.second + abs(start.second - wantStartCol)}, numR, numC))
numPaths++;
}
//diagonal the ndiagonal
}
}
*/
int main()
{
long long R, Q,C;
cin>>R>>C>>Q;
while(Q--)
{
char type; cin>>type;
long long col1, col2;
cin>>col1>>col2;
switch(type)
{
case 'P':
{
std::cout<<0<<" "<<0<<endl;
break;
}
case 'Q':{
long long qW = numQueenWays(Punkt(col1, 1), Punkt(col2, R), R, C);
if(qW == -2)
std::cout<<1<<" "<<1<<endl;
else
std::cout<<2<<" "<<qW<<endl;
break;}
case 'R':{
pair<long long, long long> rookW = calcWaysRook({1, col1}, {R, col2});
std::cout<<rookW.first<<" "<<rookW.second<<endl;
break;}
default:
{
break;
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
