QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307031#7906. Almost ConvexicesmokeWA 392ms4024kbC++144.4kb2024-01-17 20:13:532024-01-17 20:13:54

Judging History

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

  • [2024-01-17 20:13:54]
  • 评测
  • 测评结果:WA
  • 用时:392ms
  • 内存:4024kb
  • [2024-01-17 20:13:53]
  • 提交

answer

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

#define int long long 

#define fs first
#define sc second

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

class __int256 {
	public:
		const static int N=6,base=1e9;//N为压位后最大位数,base为压多少位
		int a[6],len,neg;//a存放int,len存放压位后位数,neg表示是否为负数
		__int256(__int128 x) {
			len=0;
			neg=0;
			memset(a,0,sizeof(a));
			if(x<0)x=-x,neg=1;
			int tmp;
			while((tmp=x/base)) {
				a[++len]=x%base;
				x=tmp;
			}
			a[++len]=x;
		}

		bool operator==(const __int256& x)const {
			if(len!=x.len||neg!=x.neg)return false;
			for(int i=1; i<=len; ++i)if(a[i]!=x.a[i])return false;
			return true;
		}
		bool operator!=(const __int256& x)const {
			return !(*this==x);
		}
		bool operator>(const __int256& x)const {
			if(neg!=x.neg)return x.neg;
			if(len!=x.len)return len>x.len;
			for(int i=len; i; --i)if(a[i]!=x.a[i])return a[i]>x.a[i];
			return false;
		}
		bool operator<(const __int256& x)const {
			if(neg!=x.neg)return neg;
			if(len!=x.len)return len<x.len;
			for(int i=len; i; --i)if(a[i]!=x.a[i])return a[i]<x.a[i];
			return false;
		}
		bool operator>=(const __int256& x)const {
			return !(*this < x);
		}
		bool operator<=(const __int256& x)const {
			return !(*this > x);
		}

		__int256 operator*(const __int256& x)const {
			__int256 ans=__int256(0);
			if(*this==ans||x==ans)return ans;
			if(neg!=x.neg)ans.neg=1;
			ans.len=len+x.len;
			// ull tmp;
			for(int i=1; i<=len; ++i)
				for(int j=1; j<=x.len; ++j) {
					unsigned long long tmp=1ull*a[i]*x.a[j]+ans.a[i+j-1];
					if(tmp>=base) {
						ans.a[i+j]+=tmp/base;
						ans.a[i+j-1]=tmp%base;
					} else ans.a[i+j-1]=tmp;
				}
			while(!ans.a[ans.len])
				--ans.len;
			return ans;
		}
};

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 {
		__int256 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 {
		__int256 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: 3556kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: 392ms
memory: 4024kb

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:

106

result:

wrong answer 1st numbers differ - expected: '718', found: '106'