QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714355 | #7906. Almost Convex | hanmx | TL | 0ms | 4144kb | C++17 | 4.5kb | 2024-11-05 22:46:55 | 2024-11-05 22:46:56 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using i64 = long long;
using i128 = __int128_t;
const double pi = acos(-1.0);
const double eps = 1e-10;
const double inf = 1e20;
int sgn(int x) // 判断x正负性
{
if (fabs(x) <= eps)
return 0;
else
return x < 0 ? -1 : 1;
}
int dcmp(double x, double y) // 判断x,y的大小关系(x<y返回-1)
{
if (fabs(x - y) < eps)
return 0;
else
return x < y ? -1 : 1;
}
struct Point
{
int x, y;
int id;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator+(Point B) { return Point(x + B.x, y + B.y); }
Point operator-(Point B) { return Point(x - B.x, y - B.y); }
Point operator*(double k) { return Point(x * k, y * k); }
Point operator/(double k) { return Point(x / k, y / k); }
bool operator==(Point B) { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; }
bool operator < (Point t){
return x != t.x ? x < t.x : y < t.y;
}
};
using Vector = Point;
double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y); } // 两点间距离
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; } // 点乘
double Len(Vector A) { return sqrt(Dot(A, A)); } // 求向量A的长度
double Len2(Vector A) { return Dot(A, A); } // 求向量A的长度平方
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Len(A) / Len(B)); }
// 求向量A与向量B的夹角
double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; } // 叉乘
double Area2(Point A, Point B, Point C) { return Cross(B - A, C - A); }
// 求以A,B,C三个点围成的平行四边形面积
Vector Rotate(Vector A, double rad)
{ // 向量A逆时针转rad度
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector rotate90(Vector p)
{ // 逆时针旋转90度
return Vector(-p.y, p.x);
}
Vector Normal(Vector A) { return Vector(-A.y / Len(A), A.x / Len(A)); } // 求单位法向量
bool Parallel(Vector A, Vector B) { return sgn(Cross(A, B)) == 0; }
using Points = vector<Point>;
bool lt(double a, double b) { return a - b < -eps; }
Points ConvexHull(Points poly, int n){ // Andrew算法求凸包(输入的数组下标从1开始,n为数组中的点的个数,得到一个含首尾点的数组)
vector<int> stk(n+1);
vector<bool> used(n+1);
int top=0;
sort(poly.begin() + 1,poly.begin() + n + 1,[&](Point x,Point y){
return (x.x==y.x)?(x.y<y.y):(x.x<y.x);
});
stk[++top]=1;
for(int i=2;i<=n;i++){
while(top>1&&sgn(Cross((poly[stk[top]]-poly[stk[top-1]]),(poly[i]-poly[stk[top]])))<=0){
used[stk[top--]]=0;
}
used[i]=1;
stk[++top]=i;
}
int tmp=top;
for(int i=n-1;i;i--){
if(used[i]) continue;
while(top>tmp&&sgn(Cross((poly[stk[top]]-poly[stk[top-1]]),(poly[i]-poly[stk[top]])))<=0){
used[stk[top--]]=0;
}
used[i]=1;
stk[++top]=i;
}
Points a;
for(int i=1;i<=top;i++){
a.push_back(poly[stk[i]]);
}
return a;
}
const Point O(0,0);
double theta(Point p) { return p == O ? -1 / 0. : atan2(p.y, p.x); } // 求极角
void psort(Points &ps, Point c = O) // 极角排序
{
sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
return lt(theta(p1 - c), theta(p2 - c));
});
}
void solve()
{
int n;
cin>>n;
Points p(n + 1);
for(int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y;
p[i].id=i;
}
vector<bool> used(n+1);
Points t = ConvexHull(p,n);
for(auto l:t){
used[l.id]=1;
}
ll sum = 0;
Points z(n-1);
for(int i=1;i<=n;i++)
{
if(used[i]) continue;
int cnt=0;
for(int j = 1;j <= n;j++)
{
if(i!=j)
{
z[cnt]=p[j];
cnt++;
}
}
sort(z.begin(), z.end(), [&](auto p1, auto p2) {
return lt(theta(p1 - p[i]), theta(p2 - p[i]));
});
for(int j = 1;j < n-1;j++)
{
if(used[z[j].id]&&used[z[j-1].id])
{
sum++;
}
}
if(used[z[0].id]&&used[z[n-2].id])
{
sum++;
}
}
cout<<sum + 1<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
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: 4144kb
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: 3900kb
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: 3776kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3948kb
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: 3568kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
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...