QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605273 | #7906. Almost Convex | infCraft | WA | 914ms | 3876kb | C++14 | 11.2kb | 2024-10-02 16:29:51 | 2024-10-02 16:29:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define ff first
#define ss second
#define fori(x,y) for(int i=x;i<=(int)(y);++i)
#define forj(x,y) for(int j=x;j<=(int)(y);++j)
#define fork(x,y) for(int k=x;k<=(int)(y);++k)
#define debug(x) cerr << #x << " = " << x << endl
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll MOD = 998244353;
ll qpow(ll a,ll p) {ll res=1; while(p) {if (p&1) {res=res*a%MOD;} a=a*a%MOD; p>>=1;} return res;}
namespace Geometry {
const double PI = acos(-1);
const double eps = 1e-13;
int cmp(double x, double y) { // 比较两个浮点数的大小 x<y为-1,x>y为1
if (fabs(x-y)<eps) return 0;
else return x<y?-1:1;
}
int sgn(double x) { // 符号函数,大于0为1,小于0为-1
return cmp(x, 0);
}
struct Vector {
double x, y;
Vector(): x(0), y(0) {}
Vector(double x, double y): x(x), y(y) {}
bool zero() const {
return sgn(x) == 0&&sgn(y) == 0;
}
double distance2(const Vector& B) const {
return (x-B.x)*(x-B.x)+(y-B.y)*(y-B.y);
}
double distance(const Vector& B) const {
return sqrt(distance2(B));
}
double length2() const {
return x*x+y*y;
}
double length() const {
return sqrt(length2());
}
Vector normalize() const {
return Vector(x/length(), y/length());
}
Vector operator+(const Vector& B) const {
return Vector(x+B.x, y+B.y);
}
Vector operator-(const Vector& B) const {
return Vector(x-B.x, y-B.y);
}
Vector operator*(double k) const {
return Vector(x*k, y*k);
}
Vector operator/(double k) const {
return Vector(x/k, y/k);
}
double dot(const Vector& B) const {
return x*B.x+y*B.y;
}
double operator*(const Vector& B) const {
return dot(B);
}
bool operator==(const Vector& B) const {
return sgn(x-B.x) == 0&&sgn(y-B.y) == 0;
}
double cross(const Vector& B) const { // 从自身旋转到B的叉积(注意方向,逆时针正顺时针负)
return x*B.y-y*B.x;
}
double angle(const Vector& B) const { // 计算与另一个向量的夹角(注意方向,逆时针正顺时针负)
return sgn(cross(B))*acos(dot(B)/length()/B.length());
}
bool parallel(const Vector& B) const { // 判断两个向量是否平行
return sgn(cross(B)) == 0;
}
};
struct Polygon { // 由向量构成的多边形
vector<Vector> points; // 尽量用逆时针排布
Polygon(): points(vector<Vector>()) {}
Polygon(vector<Vector> points): points(points) {}
/**
* 判断点是否在多边形内:
* 3:点在多边形顶点上
* 2:点在多边形的边上
* 1:点在多边形内部
* 0:点在多边形外部
*/
int isInPolygon(Vector point) const {
int n = points.size();
int num = 0;
fori(0, n-1) {
Vector v1 = points[i], v2 = points[(i+1)%n];
int c = sgn((point-v2).cross(v1-v2));
int u = sgn(v1.y-point.y);
int v = sgn(v2.y-point.y);
if (c>0&&u<0&&v>=0) num++;
if (c<0&&u>=0&&v<0) num--;
}
return num!=0;
}
/**
* 求多边形面积的两倍
* 但一定要注意!多边形得是逆时针排布!
*/
double area2() const {
double sum = 0;
int n = points.size();
fori(0, n-1) sum += points[i].cross(points[(i+1)%n]);
return sum;
}
double area() const { // 多边形面积
return area2()/2;
}
/**
* 求多边形的重心
*/
Vector gravityCenter() const {
Vector ans;
int n = points.size();
fori(0, n-1) {
Vector v1 = points[i], v2 = points[(i+1)%n];
ans = ans+(v1+v2)*v1.cross(v2);
}
ans = ans/area()/6;
return ans;
}
};
struct Line { // 直线
Vector p1, p2; // 两点确定一条直线
Line(Vector p1, Vector p2): p1(p1), p2(p2) {} // 基础构造方法
Line(Vector p, double angle) { // 斜率构造方法:一点+斜率,0<=angle<=pi
p1 = p;
if (sgn(angle-PI/2) == 0) {p2 = (p1+Vector(0, 1));}
else {p2 = (p1+Vector(1, tan(angle)));}
}
Line(double a, double b, double c) { // ax+by+c=0
if (sgn(a) == 0) {
p1 = Vector(0, -c/b);
p2 = Vector(1, -c/b);
}
else if (sgn(b) == 0) {
p1 = Vector(-c/a, 0);
p2 = Vector(-c/a, 1);
}
else {
p1 = Vector(0, -c/b);
p2 = Vector(1, -(c+a)/b);
}
}
// 判断一个点在直线上、左侧还是右侧
int pointLineRelation(Vector p) const {
int c = sgn((p-p1).cross(p2-p1));
if (c<0) return 1; // 1: 左侧
else if (c>0) return 2; // 2: 右侧
else return 0; // 0: 在直线上
}
// 计算点到直线的距离
double distanceToPoint(Vector p) const {
return fabs((p-p1).cross(p2-p1))/p1.distance(p2);
}
// 点在直线上的投影
Vector pointProj(Vector p) const {
double k = (p-p1).dot(p2-p1)/p1.distance2(p2);
return p1+(p2-p1)*k;
}
// 与另一条直线的位置关系
int lineRelation(const Line& B) const {
if (sgn((p2-p1).cross(B.p2-B.p1)) == 0) {
if (pointLineRelation(B.p1) == 0) return 1; // 1: 重合
else return 0; // 0: 平行
}
return 2; // 2: 相交
}
// 与另一条直线的交点(注意!两条直线必须相交!!!)
Vector crossPoint(const Line& B) const {
double s1 = (p2-p1).cross(B.p1-p1);
double s2 = (p2-p1).cross(B.p2-p1);
return Vector(B.p1.x*s2-B.p2.x*s1, B.p1.y*s2-B.p2.y*s1)/(s2-s1);
}
};
struct Circle {
Vector c; // 圆心
double r; // 半径
Circle(Vector c, double r): c(c), r(r) {}
Circle(const Vector& a, const Vector& b, const Vector& c) { // 三点定圆
double a1 = b.x-a.x, b1 = b.y-a.y, c1 = (a1*a1+b1*b1)/2;
double a2 = c.x-a.x, b2 = c.y-a.y, c2 = (a2*a2+b2*b2)/2;
double d = a1*b2-a2*b1;
Vector center(a.x+(c1*b2-c2*b1)/d, a.y+(a1*c2-a2*c1)/d);
this->c = center;
r = center.distance(a);
}
// 点和圆的位置关系
int pointCircleRelation(Vector p) const {
double d = p.distance(c);
if (sgn(d-r)<0) return 0; // 0: 点在圆内
else if (sgn(d-r)==0) return 1; // 1: 点在圆上
else return 2; // 2: 点在圆外
}
// 直线和圆的位置关系
int lineCircleRelation(const Line& line) const {
double d = line.distanceToPoint(c);
if (sgn(d-r)<0) return 0; // 0: 直线和圆相交
else if (sgn(d-r)==0) return 1; // 1: 直线和圆相切
else return 2; // 2: 直线在圆外
}
/**
* 求解直线和圆的交点
*
* @param line 直线
* @param p1 返回第一个交点
* @param p2 返回第二个交点
* @return 返回交点的个数
*/
int lineCrossCircle(const Line& line, Vector& p1, Vector& p2) const {
if (lineCircleRelation(line) == 2) return 0; // 没有交点
Vector pro = line.pointProj(c);
double d = line.distanceToPoint(c);
double k = sqrt(r*r-d*d);
if (sgn(k) == 0) {
p1 = pro, p2 = pro;
return 1; // 直线和圆相切,只有一个交点
}
Vector n = (line.p2-line.p1)/line.p2.distance(line.p1);
p1 = pro+n*k, p2 = pro-n*k;
return 2; // 两个交点
}
};
};
using namespace Geometry;
// Andrew算法求凸包
// 先求下凸包再求上凸包
// sets是按照x从小到大,y从小到大排序的点对
Polygon getConvexHull(const set<pair<double,double>>& sets) {
// 下凸包
vector<Vector> down;
for (auto it=sets.begin();it!=sets.end();++it) { // 从前到后遍历sets
Vector p(it->first, it->second);
while (down.size()>1) {
Vector p1=down[down.size()-2], p2=down.back();
if (sgn((p2-p1).cross(p-p2)) == 1) break; // 判断是否符合凸多边形
down.pop_back(); // 如果不符合,那么最后那个点需要去掉
}
down.push_back(p); // 加入最新的点
}
// 上凸包
vector<Vector> up;
for (auto it=sets.rbegin();it!=sets.rend();++it) {
Vector p(it->first, it->second);
while (up.size()>1) {
Vector p1=up[up.size()-2], p2=up.back();
if (sgn((p2-p1).cross(p-p2)) == 1) break;
up.pop_back();
}
up.push_back(p);
}
Polygon pol;
fori(0, down.size()-2) pol.points.push_back(down[i]); // up down开头和结尾的点是重复的,删掉一个
fori(0, up.size()-2) pol.points.push_back(up[i]);
return pol;
}
void solve() {
int n;
cin >> n;
set<pair<double,double>> sets;
fori(1, n) {
int x, y;
cin >> x >> y;
sets.insert({x, y});
}
vector<Vector> other;
Polygon pol = getConvexHull(sets);
for (auto pi: sets) {
Vector vec(pi.first, pi.second);
bool in = false;
for (auto v: pol.points) if (vec == v) {
in = true;
break;
}
if (!in) other.push_back(vec);
}
assert(other.size()+pol.points.size() == n);
int ans = 1;
fori(0, pol.points.size()-1) {
Polygon pol2;
pol2.points.push_back(pol.points[i]);
pol2.points.push_back(pol.points[(i+1)%n]);
for (auto v: other) {
pol2.points.push_back(v);
bool can = true;
for (auto w: other) {
if (w == v) continue;
if (pol2.isInPolygon(w)) {
can = false;
break;
}
}
if (can) ans++;
pol2.points.pop_back();
}
}
cout << ans << endl;
}
signed main() {
IOS;
int t = 1;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 914ms
memory: 3728kb
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...
output:
726
result:
wrong answer 1st numbers differ - expected: '718', found: '726'