M. Drain the Water Tank
这道题需要用到向量间的叉积运算。
首先输入所有点，储存在数组\(a\)中，并将其全部转化为向量，储存在数组\(b\)中。
为了排尽水箱里的所有水，需要找到每一个属于水箱内容物局部最低块中的一个点。
所以可以将判断分为两步
- 判断是否为局部最低点：当\(b[i].y < 0\)且\(b[i + 1].y>0\)时，\(b[i]\)的终点即为局部最低点。但是，会有\(\searrow\)___\(\nearrow\)的情况，所以可以改为\(b[i].y <= 0\)且\(b[i + 1].y>0\)，\(b[i]\)的终点作为整个局部的最低点。
- 判断是否为水箱内容物的最底部，因为题目是逆时针给出各点的，所以当\(b[i]\times b[i + 1]>0\)且满足①时，需要在\(b[i]\)的终点处挖洞。
按照以上方法，该题会Wa30。
代码(Wa30)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const double eps = 1e-8;
const double PI = acos(-1.0);
int sgn(double x)
{
if (fabs(x) < eps)
return 0;
if (x < 0)
return -1;
else
return 1;
}
struct Point
{
int x, y;
Point(){}
Point(double _x, double _y) : x(_x), y(_y){}
Point operator+(const Point &b) const{return Point(x + b.x, y + b.y);}
Point operator-(const Point &b) const{return Point(x - b.x, y - b.y);}
double operator^(const Point &b) const{return (x * b.y - y * b.x);} //叉乘
double operator*(const Point &b) const{return (x * b.x + y * b.y);} //点乘
bool operator<(const Point &b) const{return x < b.x || x == b.x && y < b.y;}
bool operator==(const Point &b) const{return !sgn(x - b.x) && !sgn(y - b.y);}
Point rotate(Point p, double B)
{
Point tmp;
tmp.x = (x - p.x) * cos(B) - (y - p.y) * sin(B) + p.x;
tmp.y = (x - p.x) * sin(B) + (y - p.y) * cos(B) + p.y;
return tmp;
}
};
const int N = 2e3 + 10;
int n;
Point a[N];
vector<Point> b;
signed main()
{
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++)
{
int x, y;
cin >> a[i].x >> a[i].y;
}
a[n] = a[0];
for(int i = 0;i < n;i++)
{
b.push_back(a[i + 1] - a[i]);
}
b[n] = b[0];
int ans = 0;
for(int i = 0;i < n;i++)
{
if((b[i] ^ b[i + 1]) > 0 && b[i].y <= 0 && b[i + 1].y > 0)
{
ans++;
}
}
cout << ans;
return 0;
}
因为上面的方法在遇到楼梯式的点时会把每一个→↑的点当作局部最低点，所以要先将向量的数组复制一倍，然后找到\(y<0\)的向量并从该向量开始遍历，新增一个变量\(fu\)，每遇到一个\(y<0\)的向量都将\(fu = true\)，当满足上面的①、②且\(fu=true\)时才挖洞，并把\(fu\)赋值为\(false\)。
这样又会得到一份Wa83的代码
代码(Wa83)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const double eps = 1e-8;
const double PI = acos(-1.0);
int sgn(double x)
{
if (fabs(x) < eps)
return 0;
if (x < 0)
return -1;
else
return 1;
}
struct Point
{
int x, y;
Point(){}
Point(double _x, double _y) : x(_x), y(_y){}
Point operator+(const Point &b) const{return Point(x + b.x, y + b.y);}
Point operator-(const Point &b) const{return Point(x - b.x, y - b.y);}
double operator^(const Point &b) const{return (x * b.y - y * b.x);} //叉乘
double operator*(const Point &b) const{return (x * b.x + y * b.y);} //点乘
bool operator<(const Point &b) const{return x < b.x || x == b.x && y < b.y;}
bool operator==(const Point &b) const{return !sgn(x - b.x) && !sgn(y - b.y);}
Point rotate(Point p, double B)
{
Point tmp;
tmp.x = (x - p.x) * cos(B) - (y - p.y) * sin(B) + p.x;
tmp.y = (x - p.x) * sin(B) + (y - p.y) * cos(B) + p.y;
return tmp;
}
};
const int N = 2e3 + 10;
int n;
Point a[N];
vector<Point> b;
signed main()
{
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++)
{
int x, y;
cin >> a[i].x >> a[i].y;
}
a[n] = a[0];
for(int i = 0;i < n;i++)
{
b.push_back(a[i + 1] - a[i]);
}
b[n] = b[0];
int ans = 0;
int now = 0;
b.insert(b.end(), b.begin(), b.end());
for(now = 0;b[now].y >= 0;)
{
now++;
}
int xx = now;
bool fu = 0;
for(int i = now;i < now + n;i++)
{
//cout << xx << " " << (b[xx] ^ b[i]);
if(b[i].y < 0)
fu = 1;
if((b[i] ^ b[i + 1]) > 0 && b[i].y <= 0 && b[i + 1].y > 0 && fu)
{
ans++;
//cout << " ++";
fu = 0;
}
//cout << endl;
}
cout << ans;
return 0;
}
原因是没有考虑这个点的情况，所以要在满足条件①时也把\(fu\)赋值为\(false\)
时间复杂度为\(O(n)\)
正解代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const long double eps = 1e-8;
const long double PI = acos(-1.0);
ll sgn(long double x)
{
if (fabs(x) < eps)
return 0;
if (x < 0)
return -1;
else
return 1;
}
struct Point
{
int x, y;
Point() {}
Point(long double _x, long double _y) : x(_x), y(_y) {}
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
long double operator^(const Point &b) const { return (x * b.y - y * b.x); } // 叉乘
long double operator*(const Point &b) const { return (x * b.x + y * b.y); } // 点乘
bool operator<(const Point &b) const { return x < b.x || x == b.x && y < b.y; }
bool operator==(const Point &b) const { return !sgn(x - b.x) && !sgn(y - b.y); }
Point rotate(Point p, long double B)
{
Point tmp;
tmp.x = (x - p.x) * cos(B) - (y - p.y) * sin(B) + p.x;
tmp.y = (x - p.x) * sin(B) + (y - p.y) * cos(B) + p.y;
return tmp;
}
};
const ll N = 2e3 + 10;
ll n;
Point a[N];
vector<Point> b;
signed main()
{
// std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (ll i = 0; i < n; i++)
{
ll x, y;
cin >> a[i].x >> a[i].y;
}
a[n] = a[0];
for (ll i = 0; i < n; i++)
{
b.push_back(a[i + 1] - a[i]);
}
b[n] = b[0];
ll ans = 0;
ll now = 0;
b.insert(b.end(), b.begin(), b.end());
for (now = 0; b[now].y >= 0;)
{
now++;
}
ll xx = now;
bool fu = 0;
for (ll i = now; i < now + n; i++)
{
// cout << xx << " " << (b[xx] ^ b[i]);
if (b[i].y < 0)
fu = 1;
if (b[i].y <= 0 && b[i + 1].y > 0 && fu)
{
// cout << " ++";
fu = 0;
if((b[i] ^ b[i + 1]) > 0)
{
ans++;
}
}
// cout << endl;
}
cout << ans;
return 0;
}