QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605354 | #7906. Almost Convex | infCraft | TL | 958ms | 4052kb | C++14 | 11.5kb | 2024-10-02 16:47:56 | 2024-10-02 16:47:56 |
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)%pol.points.size()]);
Line line(pol.points[i], pol.points[(i+1)%pol.points.size()]);
sort(other.begin(), other.end(), [&](const Vector& v1, const Vector& v2) -> bool {
return line.distanceToPoint(v1)<line.distanceToPoint(v2);
});
forj(0, other.size()-1) {
pol2.points.push_back(other[j]);
bool can = true;
fork(0, j-1) {
if (pol2.isInPolygon(other[k])) {
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: 3784kb
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: 3788kb
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: 3820kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
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: 0ms
memory: 3488kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 18ms
memory: 3848kb
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:
718
result:
ok 1 number(s): "718"
Test #7:
score: 0
Accepted
time: 16ms
memory: 3748kb
input:
2000 571314 -128802 -57762 485216 -713276 485201 -385009 -844644 371507 403789 338703 -272265 -913641 438001 -792118 -481524 709494 213762 -913577 432978 -397111 709021 840950 328210 -843628 452653 -20721 126607 -107804 -338102 930109 -89787 -949115 -76479 -862141 455623 991761 94852 -635475 625573 ...
output:
658
result:
ok 1 number(s): "658"
Test #8:
score: 0
Accepted
time: 10ms
memory: 3756kb
input:
2000 -510540 -289561 -602648 -189950 -403224 944455 -369582 -41334 358122 -598933 -817147 470207 -440180 -735160 -705634 61719 319062 897001 -905089 -755682 -408371 -520115 -423336 548115 -590242 835990 208155 883477 -202087 142035 -71545 411206 570690 -673204 -228451 -903435 -732876 -570271 -246755...
output:
309
result:
ok 1 number(s): "309"
Test #9:
score: 0
Accepted
time: 9ms
memory: 3816kb
input:
2000 -532115 566389 138405 49337 398814 -97324 116833 113216 381728 877609 222402 641022 109920 952381 -113880 395181 13780 -572931 -676608 605202 -74328 -503839 -207767 926500 -663270 -146303 197877 280349 275865 -663892 -630214 3286 973786 304855 -493735 841584 394901 -505975 757960 204724 -373328...
output:
239
result:
ok 1 number(s): "239"
Test #10:
score: 0
Accepted
time: 22ms
memory: 4052kb
input:
2000 512636 509804 -661126 -592269 755566 -721837 -878213 441853 -236050 -89069 -181220 155656 203391 691764 940154 260513 747075 373881 620423 840991 -409624 335472 270937 -710659 -751290 -673585 250341 -193243 -250535 618887 -739996 543936 -547741 -213681 -82920 -364319 -611672 737719 930798 46731...
output:
1025
result:
ok 1 number(s): "1025"
Test #11:
score: 0
Accepted
time: 9ms
memory: 3780kb
input:
2000 943353 817289 237151 899722 682851 -464873 854225 205354 834550 257948 -260874 298196 -224572 -269157 -667301 881130 -45920 -696359 -634337 792620 -408527 -947513 582880 172669 921645 839423 833813 721080 -836662 -287230 -55783 -408594 108996 -122012 365647 -789544 313812 833502 970009 -737736 ...
output:
218
result:
ok 1 number(s): "218"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
2000 619248 227987 -252490 -553032 148050 -479727 -333707 -591482 -40488 -503144 561909 255624 -402541 -798967 -245811 -610006 -146584 -517935 226433 -92580 -81939 -828480 72540 -845547 502613 220323 66708 -573015 601886 258752 406443 257854 232970 -671600 -37023 -683767 602339 456757 -440096 -71899...
output:
7
result:
ok 1 number(s): "7"
Test #13:
score: 0
Accepted
time: 3ms
memory: 3780kb
input:
2000 -602451 2956 85982 141739 -185932 -208897 -716095 58215 -468047 155612 -791626 -3105 75700 -484098 609608 -304849 689485 -106857 533177 -285261 -659400 -241162 -369302 165482 406663 265940 -353843 -788313 805885 -75440 -571955 -60471 351360 -81373 -510926 -59456 591713 179588 534794 -118 201630...
output:
66
result:
ok 1 number(s): "66"
Test #14:
score: 0
Accepted
time: 3ms
memory: 3748kb
input:
2000 41203 -675424 -158994 366628 -133859 -595680 435466 687630 687811 -35017 314337 133049 -384711 444777 54850 -760922 526166 282618 572292 94793 -324003 621393 -30308 242225 612969 -231837 -56628 -892609 -492077 58749 29597 -349591 198510 219502 380955 -59845 839171 -40068 88185 -820614 -572977 -...
output:
43
result:
ok 1 number(s): "43"
Test #15:
score: 0
Accepted
time: 4ms
memory: 3980kb
input:
2000 -814040 46114 -324077 -522697 388552 -604274 -252898 43028 -757069 141507 413462 -649779 -281915 -316285 -498931 -573214 -408766 670792 -271435 -393170 87187 731739 89312 -853584 -768680 -307261 -185324 234729 -70493 -354866 16452 164338 -650791 -518077 851196 -259322 -85395 -509349 241593 5074...
output:
129
result:
ok 1 number(s): "129"
Test #16:
score: 0
Accepted
time: 26ms
memory: 3752kb
input:
2000 23103 -796677 -148322 67634 -525131 -446626 2672 584671 -712789 -69579 -91150 -429393 -375635 -487235 -680553 -370975 793181 -383683 -234131 -462420 -734705 -171834 322671 -355011 760005 224249 700248 -352775 416862 -125857 -497951 717254 677084 -451876 -220123 616240 525973 -144881 -300828 553...
output:
1466
result:
ok 1 number(s): "1466"
Test #17:
score: 0
Accepted
time: 37ms
memory: 3808kb
input:
2000 -185174 470373 -772343 -70370 -182314 851727 661615 -250979 -581175 527646 332025 141502 -659052 -506788 -378459 -553180 11233 162287 469975 -572356 679074 217029 -137967 727723 581696 140544 452574 -319370 120895 129820 772655 -330960 122860 823902 -786221 147543 -206152 -373647 -212943 4820 6...
output:
2801
result:
ok 1 number(s): "2801"
Test #18:
score: 0
Accepted
time: 209ms
memory: 3696kb
input:
2000 -718158 695879 655921 595312 -509080 -860718 540612 244159 -83221 -865654 -460513 -542465 102321 -775593 328552 799263 -284269 -725108 152140 549502 -108610 465054 -97837 -449762 -772869 -171472 293831 -711723 508617 -157976 170737 323070 544222 385453 -633043 -233165 -620164 -459706 507218 338...
output:
14445
result:
ok 1 number(s): "14445"
Test #19:
score: 0
Accepted
time: 958ms
memory: 3752kb
input:
2000 -587991 -165467 -530325 -5525 -574943 180654 -496535 -748102 -436469 -160646 110285 237070 -822862 -141480 -177189 327799 -424868 331309 -999274 38095 -745710 192605 -234174 -804258 586432 -176239 -626756 499109 -562606 826724 890245 455480 -32262 -298900 550800 516690 -588632 -368654 405331 -3...
output:
64358
result:
ok 1 number(s): "64358"
Test #20:
score: -100
Time Limit Exceeded
input:
2000 441575 -414673 651578 -449237 287355 -489950 606811 -30288 -733692 679481 -652568 89883 -360110 616801 190405 -368787 -352383 935855 118240 73038 -374899 -927065 -22183 -491455 -146229 638417 998825 -48442 -374469 243261 988830 149043 -778607 -291542 -277026 -167975 372912 -405043 535321 425727...