QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#663282#7906. Almost Convexxiaolei338WA 5ms3812kbC++2011.1kb2024-10-21 14:37:292024-10-21 14:37:29

Judging History

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

  • [2024-10-21 14:37:29]
  • 评测
  • 测评结果：WA
  • 用时：5ms
  • 内存：3812kb
查看
  • [2024-10-21 14:37:29]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 2e5 + 10, mod = 998244353, INF = 0x3f3f3f3f;
random_device rd;
mt19937_64 rng(rd());

LL n, m;
LL a[N];

const double eps = 1e-10;

inline bool equals(double a, double b)//判断相等
{
    return fabs(a - b) < eps;
}

int sgn(double a){ //误差 
	if(fabs(a)<eps) return 0;
	return a>0?1:-1;
}

struct Point//点 向量
{
    double x, y;
    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 equals(x, b.x) ? y < b.y : x < b.x;
    }
};
// typedef Point Vector;

inline double get_atan2(Point a, Point b)//求极角
{
    Point v = b - a;
    return atan2(v.y, v.x);
}

struct Segment//线段 直线 射线
{
    Point p1, p2;//若表示射线则起点为p1
    double ang;
    Segment() {}
    Segment(Point a, Point b) :p1(a), p2(b), ang(get_atan2(p1, p2)) {}
};
typedef Segment Line;

struct Circle//圆
{
    Point c;
    double r;
    Circle() {}
    Circle(Point c, double r) :c(c), r(r) {}
};

typedef vector<Point> Polygon;//多边形

double norm(Point a)//范数
{
    return pow(a.x, 2) + pow(a.y, 2);
}

double abs(Point a)//模长
{
    return sqrt(norm(a));
}

double dot(Point a, Point b)//|a||b|cos A
{
    return a.x * b.x + a.y * b.y;
}

inline double cross(Point a, Point b)//|a||b|sin A
{
    return a.x * b.y - a.y * b.x;
}

bool isOrthogonal(Point a, Point b)//判断正交
{
    return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2)
{
    return isOrthogonal(a1 - a2, b1 - b2);
}

bool isOrthogonal(Segment s1, Segment s2)
{
    return isOrthogonal(Point(s1.p1 - s1.p2), Point(s2.p1 - s2.p2));
}

bool isParallel(Point a, Point b)//判断平行
{
    return equals(cross(a, b), 0.0);
}

bool isParallel(Point a1, Point a2, Point b1, Point b2)
{
    return isParallel(a1 - a2, b1 - b2);
}

bool isParallel(Segment s1, Segment s2)
{
    return isParallel(Point(s1.p1 - s1.p2), Point(s2.p1 - s2.p2));
}

Point project(Point p, Segment s)//求投影
{
    Point base = s.p2 - s.p1;
    double r = dot(p - s.p1, base) / norm(base);
    base = base * r;
    return Point(s.p1 + base);
}

Point reflect(Point p, Segment s)//求映射
{
    Point p1 = (project(p, s) - p) * 2.0;
    return p + p1;
}

double get_dis(Point a, Point b)//求点之间距离
{
    return abs(a - b);
}

double get_dis(Point a, Line l)//求点与直线之间距离
{
    return abs(cross(l.p2 - l.p1, a - l.p1) / abs(l.p2 - l.p1));
}

double get_dis_ps(Point p, Segment s)//求点与线段距离
{
    if (dot(p - s.p1, s.p2 - s.p1) < 0.0) return abs(p - s.p1);
    if (dot(p - s.p2, s.p1 - s.p2) < 0.0) return abs(p - s.p2);
    return get_dis(p, s);
}

inline bool intersect(Point, Point, Point, Point);
inline bool intersect(Segment, Segment);

double get_dis_ss(Segment a, Segment b)//求线段之间距离
{
    if (intersect(a, b)) return 0.0;
    return min(min(get_dis_ps(a.p1, b), get_dis_ps(a.p2, b)), min(get_dis_ps(b.p1, a), get_dis_ps(b.p2, a)));
}

//b在a的
const int CC = 1;//逆时针方向
const int C = -1;//顺时针方向
const int OB = 2;//方向相反
const int OF = -2;//方向相同 |b|>|a|
const int OS = 0;//方向相同 |a|>|b|

inline int ccw(Point p1, Point p2, Point p3)//判断三点的位置关系
{
    Point a = p2 - p1;
    Point b = p3 - p1;
    if (cross(a, b) > eps) return CC;
    if (cross(a, b) < -eps) return C;
    if (dot(a, b) < -eps) return OB;
    if (norm(a) < norm(b)) return OF;
    return OS;
}

inline int ccw(Point a, Point b)//判断向量的位置关系
{
    if (cross(a, b) > eps) return CC;
    if (cross(a, b) < -eps) return C;
    if (dot(a, b) < -eps) return OB;
    if (norm(a) < norm(b)) return OF;
    return OS;
}

inline bool intersect(Point a, Point b, Point c, Point d)//判断两线段相交
{
    return ccw(a, b, c) * ccw(a, b, d) <= 0 && ccw(c, d, a) * ccw(c, d, b) <= 0;
}

inline bool intersect(Segment a, Segment b)
{
    return intersect(a.p1, a.p2, b.p1, b.p2);
}

Point getCrossPoint_Line(Line s1, Line s2)//求两直线交点
{
    Point v1, v2;
    v1 = s1.p2 - s1.p1, v2 = s2.p2 - s2.p1;
    Point u = s1.p1 - s2.p1;
    double t = cross(v2, u) / cross(v1, v2);

    Point x = v1 * t;
    return s1.p1 + x;
}

Point getCrossPoint(Segment s1, Segment s2, bool flag = 0)//求两线段交点
{
    if (!intersect(s1, s2))
    {
        if (flag) return getCrossPoint_Line(s1, s2);
        else return Point(1e18, 1e18);
    }

    Point base = s2.p2 - s2.p1;
    double d1 = abs(cross(base, s1.p1 - s2.p1));
    double d2 = abs(cross(base, s1.p2 - s2.p1));
    double t = d1 / (d1 + d2);
    Point x = (s1.p2 - s1.p1) * t;
    return s1.p1 + x;
}

pair<Point, Point> getCrossPoint(Line l, Circle C)//求直线与圆交点
{
    if (get_dis(C.c, l) > C.r) return make_pair(Point(2e18, 2e18), Point(2e18, 2e18));

    Point pr = project(C.c, l);
    Point e = (l.p2 - l.p1) / abs(l.p2 - l.p2);
    double base = sqrt(C.r * C.r - norm(pr - C.c));
    Point x = e * base;
    return make_pair(pr + x, pr - x);
}

inline Polygon andrewScan(Polygon p)//求凸包
{
    Polygon u, d;
    if (p.size() < 3) return p;
    sort(p.begin(), p.end());

    u.push_back(p[0]);
    u.push_back(p[1]);

    d.push_back(p[p.size() - 1]);
    d.push_back(p[p.size() - 2]);

    for (int i = 2; i < p.size(); i++)
    {
        for (int k = u.size(); k >= 2 && ccw(u[k - 2], u[k - 1], p[i]) != C; k--) u.pop_back();
        u.push_back(p[i]);
    }

    for (int i = p.size() - 3; ~i; i--)
    {
        for (int k = d.size(); k >= 2 && ccw(d[k - 2], d[k - 1], p[i]) != C; k--) d.pop_back();
        d.push_back(p[i]);
    }

    reverse(d.begin(), d.end());
    for (int i = u.size() - 2; i; i--) d.push_back(u[i]);
    return d;
}

double RoatingCalipers(vector<Point> poly){// 旋转卡壳求直径
    poly.push_back(poly[0]);
    if(poly.size()==3) return get_dis(poly[0], poly[1]);
    int cur=0;
    double ans=0;
    for(int i=0;i<poly.size()-1;i++){
        Line line(poly[i],poly[i+1]);
        while(get_dis(poly[cur], line) <= get_dis(poly[(cur+1)%poly.size()], line)){
            cur=(cur+1)%poly.size();
        }
        ans=max(ans, max(get_dis(poly[i], poly[cur]), get_dis(poly[i+1],poly[cur])));
    }
    return ans;
}

Line mnd;
Point mna, mnla, mnra;
double get_minest(vector<Point> poly){// 旋转卡壳求最小矩形覆盖
	int j=2,l=1,r=1,t=poly.size();
	double t1,t2,t3,ans=-1;
    poly.push_back(poly[0]);
	for(int i=0;i<t-1;i++){//i,i+1为矩形底 ,设长度为d 
		while(fabs(cross((poly[(i+1)%t]-poly[i]),(poly[j]-poly[i])))<fabs(cross((poly[(i+1)%t]-poly[i]),(poly[(j+1)%t]-poly[i])))) j=(j+1)%t;//矩形上端 
		while(sgn(dot((poly[i+1]-poly[i]),(poly[r+1]-poly[i]))-dot((poly[i+1]-poly[i]),(poly[r]-poly[i])))>0) r=(r+1)%t;//矩形右端(相对于矩形底) 
		l=max(l,j);// l必须比j大 ，既在逆时针方向上的下一个点 
		while(sgn(dot((poly[i+1]-poly[i]),(poly[l+1]-poly[i]))-dot((poly[i+1]-poly[i]),(poly[l]-poly[i])))<0) l=(l+1)%t;//矩形左端 
		
		t1=fabs(cross((poly[i]-poly[i+1]),(poly[j]-poly[i+1])));//h*d 
		t2=fabs(dot((poly[i+1]-poly[i]),(poly[r]-poly[i])))+fabs(dot((poly[i+1]-poly[i]),(poly[l]-poly[i])));//l1*d+l2*d 
		t3=dot(poly[i+1]-poly[i], poly[i+1]-poly[i]);//d*d 
		
		double ins=t1*t2/t3;//s= (l1+l2)*h 
		if(ans<0||ans>ins){
			ans=ins;
			mnd=Segment(poly[i],poly[i+1]);
			mna=poly[j];
			mnla=poly[l];
			mnra=poly[r];
		} 
	}
    return ans;
}


void get_minest_output(){//输出矩形四个坐标
	// cout<<fixed<<setprecision(6)<<ans<<'\n';
	Point pt[5];//方向保持l->r即可保证逆时针,因为此代码求的凸包方向就是逆时针 
	pt[0]=project(mnla,mnd);//左下(相对于直线d) 
	pt[1]=project(mnra,mnd);//右下	
	Line de=Segment(mna,mna+mnd.p1-mnd.p2);//上端点所过直线,且和底边平行 
	pt[2]=project(mnra,de);//右上	
	pt[3]=project(mnla,de);//左上 
	
	for(int i=0;i<4;i++){
		printf("%.6lf %.6lf\n", pt[i].x, pt[i].y);
	}
}

inline bool cmp_ang(Segment a, Segment b)//极角排序
{
    return a.ang < b.ang;
}

inline bool OnLeft(Point p, Line s)
{
    return cross(s.p2 - s.p1, p - s.p1) > 0.0;
}

inline Polygon HPI(vector<Segment> L)//求半平面交
{
    int n = L.size();
    sort(L.begin(), L.end(), cmp_ang);

    int head, tail;
    vector<Point> p(n);
    vector<Segment> q(n);
    vector<Point> ans;

    q[head = tail = 0] = L[0];
    for (int i = 1; i < n; i++)
    {
        while (head < tail && !OnLeft(p[tail - 1], L[i])) tail--;
        while (head < tail && !OnLeft(p[head], L[i])) head++;
        q[++tail] = L[i];

        if (equals(cross(q[tail].p2 - q[tail].p1, q[tail - 1].p2 - q[tail - 1].p1), 0.0))
        {
            tail--;
            if (OnLeft(L[i].p1, q[tail])) q[tail] = L[i];
        }
        if (head < tail) p[tail - 1] = getCrossPoint(q[tail - 1], q[tail], 1);
    }

    while (head < tail && !OnLeft(p[tail - 1], q[head])) tail--;
    if (head == tail) return ans;
    p[tail] = getCrossPoint(q[tail], q[head], 1);
    for (int i = head; i <= tail; i++) ans.push_back(p[i]);
    return ans;
}

inline double Ploygon_area(Polygon s)//求多边形面积
{
    int n = s.size();
    double ans = 0.0;
    for (int i = 0; i < n; i++)
    {
        ans += cross(s[i], s[(i + 1) % n]);
    }
    return ans * 0.5;
}

void solve()
{
    Polygon p, ch;
    cin >> n;
    set<PII> se;
    for(int i = 1; i <= n; i ++)
    {
        int x, y;
        cin >> x >> y;
        se.insert({x, y});
        p.push_back({x, y});
    }
    auto v = andrewScan(p);
    for(auto [x, y] : v)
    {
        se.erase({x, y});
        // cout << x << ' ' << y << '\n';
    }
    for(auto [x, y] : se)ch.push_back({x, y});
    if(ch.empty()){
        cout << 1 << '\n';
        return;
    }
    auto cmp = [&](Point l, Point r){return sgn(cross(l, r)) > 0;};
    auto work = [&](int i){
        for(auto &p : ch)p = p - v[i];
        sort(ch.begin(), ch.end(), cmp);
        for(auto &p : ch)p = p + v[i];
    };
    LL res = 1;
    for(int i = 0; i < v.size(); i ++)
    {
        work(i);
        res ++;
        Point xx = ch[0];
        for(int j = 1; j < ch.size(); j ++)
        {
            if(sgn(cross(ch[j] - v[i + 1], xx - v[i + 1])) < 0){
                res ++;
                xx = ch[j];
            }
        }
    }
    cout << res << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    LL _T = 1;
    // cin >> _T;
    while(_T --)
    {
        solve();
    }
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3628kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: 5ms
memory: 3812kb

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:

794

result:

wrong answer 1st numbers differ - expected: '718', found: '794'
English 繁體中文 简体中文

服务器时间: 2024-11-30 11:51:55 | 开源项目