QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714340#7906. Almost ConvexhanmxTL 0ms4180kbC++174.6kb2024-11-05 22:42:402024-11-05 22:42:40

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 22:42:40]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4180kb
  • [2024-11-05 22:42:40]
  • 提交

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(double 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 B){
        return sgn(x - B.x) < 0 ||(sgn(x - B.x) == 0 && sgn(y - B.y) < 0);
        //先对x排序,再对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;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3944kb

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: 4180kb

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: 3812kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4100kb

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: 3608kb

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...

output:


result: