QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307021#7906. Almost ConvexicesmokeTL 0ms3840kbC++145.7kb2024-01-17 19:59:192024-01-17 19:59:21

Judging History

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

  • [2024-01-17 19:59:21]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3840kb
  • [2024-01-17 19:59:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long 

#define fs first
#define sc second

class BigInteger {
private:
    std::vector<int> digits;
    bool isNegative;

public:
    BigInteger() : isNegative(false) {}

     BigInteger(const std::string &num) {
        if (num[0] == '-') {
            isNegative = true;
            for (int i = num.size() - 1; i > 0; --i) {
                digits.push_back(num[i] - '0');
            }
        } else {
            isNegative = false;
            for (int i = num.size() - 1; i >= 0; --i) {
                digits.push_back(num[i] - '0');
            }
        }
    }

    BigInteger(__int128 num) {
        if (num < 0) {
            isNegative = true;
            num = -num;
        } else {
            isNegative = false;
        }

        while (num > 0) {
            digits.push_back(num % 10);
            num /= 10;
        }
    }

    BigInteger operator+(const BigInteger &other) const {
        BigInteger result;
        int carry = 0;
        int maxSize = std::max(digits.size(), other.digits.size());
        for (int i = 0; i < maxSize || carry; ++i) {
            if (i == result.digits.size()) {
                result.digits.push_back(0);
            }
            int sum = carry;
            if (i < digits.size()) {
                sum += digits[i];
            }
            if (i < other.digits.size()) {
                sum += other.digits[i];
            }
            result.digits[i] = sum % 10;
            carry = sum / 10;
        }
        return result;
    }

    BigInteger operator*(const BigInteger &other) const {
        BigInteger result;
        result.digits.resize(digits.size() + other.digits.size(), 0);
        for (size_t i = 0; i < digits.size(); ++i) {
            int carry = 0;
            for (size_t j = 0; j < other.digits.size() || carry; ++j) {
                long long sum = result.digits[i + j] + digits[i] * 1LL * (j < other.digits.size() ? other.digits[j] : 0) + carry;
                result.digits[i + j] = sum % 10;
                carry = sum / 10;
            }
        }
        while (result.digits.size() > 1 && result.digits.back() == 0) {
            result.digits.pop_back();
        }
        result.isNegative = isNegative ^ other.isNegative;
        return result;
    }

    // 大小判断的重载
    bool operator>(const BigInteger &other) const {
        if (isNegative != other.isNegative) {
            return other.isNegative;
        }
        if (digits.size() != other.digits.size()) {
            return (digits.size() > other.digits.size()) ^ isNegative;
        }
        for (int i = digits.size() - 1; i >= 0; --i) {
            if (digits[i] != other.digits[i]) {
                return (digits[i] > other.digits[i]) ^ isNegative;
            }
        }
        return false;
    }

    // 打印大整数
    void print() const {
        if (isNegative) {
            std::cout << '-';
        }
        for (int i = digits.size() - 1; i >= 0; --i) {
            std::cout << digits[i];
        }
        std::cout << std::endl;
    }
};

struct point{
	int x,y;
};



bool cmp(point p1,point p2)
{
	if(p1.x!=p2.x) return p1.x<p2.x;
	return p1.y<p2.y;
}

__int128 gcd(__int128 a,__int128 b)
{
	return b?gcd(b,a%b):a;	
}

struct frac{
	__int128 x,y;
	frac(__int128 x1,__int128 y1){
		__int128 x1i = x1*(x1>=0?1:-1);
		__int128 y1i = y1*(y1>=0?1:-1);
		__int128 g = gcd(x1i,y1i);
		x = x1/g,y = y1/g;
	}
	bool operator<(frac it) const {
		BigInteger v1(x),v2(it.y),v3(it.x),v4(y);
		return !(v1*v2 > v3*v4);
		// return x*it.y < it.x*y;
	}
	bool operator>(frac it) const {
		BigInteger v1(x),v2(it.y),v3(it.x),v4(y);
		return v1*v2 > v3*v4;
		// return x*it.y > it.x*y;
	}
};

frac getAngle(point A,point B,point C)
{
	__int128 x1 = B.x - A.x,y1 = B.y - A.y;
	__int128 x2 = C.x - A.x,y2 = C.y - A.y;
	__int128 up = (x1*x2 + y1*y2)*(x1*x2 + y1*y2);
	__int128 down = (x1*x1+y1*y1)*(x2*x2+y2*y2);
	return frac(up,down);
}

int check(point a1,point a2,point b)
{
	int v1 = (b.y - a2.y)*(a2.x - a1.x);
	int v2 = (a2.y - a1.y)*(b.x - a2.x);
	if(v1==v2) return 0;
	return v1>v2?1:-1;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int n;
	cin>>n;
	vector<point>ar(n);
	for(int i=0;i<n;i++){
		cin>>ar[i].x>>ar[i].y;
	}
	sort(ar.begin(),ar.end(),cmp);
	
	int m = 0;
	vector<int>st(n,0);
	vector<pair<point,int>>br;
	if(ar.size()<=3){
		for(int i=0;i<n;i++){
			br.push_back({ar[i],i});
		}
	}else{
		int id = 0;
		st[0] = st[1] = 1;
		br.push_back({ar[0],0});
		for(int i=1;i<n;i++){
			while(br.size()>=2 && check(br[br.size()-2].fs,br[br.size()-1].fs,ar[i])<=0){
				pair<point,int> t = br.back();
				st[t.sc] = 0;
				br.pop_back();	
			}
			st[i] = 1;
			br.push_back({ar[i],i});
		}
		m = br.size();
		br.push_back({ar[n-2],n-2});
		for(int i=n-2;i>=0;i--){
			if(st[i]) continue;
			while(br.size()>m && check(br[br.size()-2].fs,br[br.size()-1].fs,ar[i])<=0){
				pair<point,int> t = br.back(); 
				st[t.sc] = 0;
				br.pop_back();	
			}
			st[i] = 1;
			br.push_back({ar[i],i});
		}
	}
	m = br.size();
	for(auto it:br) st[it.sc] = 1;
	int ans = 0;
	for(int i=0;i<m;i++){
		vector<double>tmp1;
		vector<array<frac,2>>tmp;
		for(int j=0;j<n;j++){
			if(st[j]) continue;
			frac v1 = getAngle(br[i].fs,br[(i+1)%m].fs,ar[j]);
			frac v2 = getAngle(br[(i+1)%m].fs,br[i].fs,ar[j]);
			tmp.push_back({v1,v2});
		}
		sort(tmp.begin(),tmp.end(),greater<array<frac,2>>());
		set<frac>nums;
		for(auto it:tmp){
			int flag = 1;
			if(nums.lower_bound(it[1])!=nums.end()) flag = 0;
			nums.insert(it[1]);
			ans += flag;
		}
	}
	cout<<ans+1;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: