QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#306998#7906. Almost ConvexicesmokeTL 1ms3948kbC++143.3kb2024-01-17 19:16:282024-01-17 19:16:28

Judging History

This is the latest submission verdict.

  • [2024-01-17 19:16:28]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3948kb
  • [2024-01-17 19:16:28]
  • Submitted

answer

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

#define int long long 

const double eps = 1e-6;

#define fs first
#define sc second

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;
}

double getAngle(point A,point B,point C)
{
	int x1 = B.x - A.x,y1 = B.y - A.y;
	int x2 = C.x - A.x,y2 = C.y - A.y;
	double up = x1*x2 + y1*y2;
	double down = sqrt(pow(x1,2)+pow(y1,2))*sqrt(pow(x2,2)+pow(y2,2));
	return acos(up/down);
}

int check(point a1,point a2,point b)
{
	int v1 = (b.y - a2.y)*(a2.x - a1.x);
	// (b.y-a2.y)/(b.x-a2.x) 
	// (a2.y-a1.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();
		// for(auto it:br){
			// cout<<it.fs.x<<' '<<it.fs.y<<'\n';
		// }
		// cout<<'\n';
		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});
		}
	}
	// for(auto it:br){
		// cout<<it.fs.x<<' '<<it.fs.y<<'\n';
	// }
	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<double,2>>tmp;
		for(int j=0;j<n;j++){
			if(st[j]) continue;
			double v1 = getAngle(br[i].fs,br[(i+1)%m].fs,ar[j]);
			double v2 = getAngle(br[(i+1)%m].fs,br[i].fs,ar[j]);
			tmp.push_back({v1,v2});
			tmp1.push_back(v1),tmp1.push_back(v2);
			// cout<<v1<<' '<<v2<<'\n';
			int add = 1;
			for(int k=0;k<n;k++){
				if(st[k] || j==k) continue;
				double v1i = getAngle(br[i].fs,br[(i+1)%m].fs,ar[k]);
				double v2i = getAngle(br[(i+1)%m].fs,br[i].fs,ar[k]);
				int f1 = v1i>v1 || (fabs(v1i-v1)<=1e-5);
				int f2 = v2i>v2 || (fabs(v2i-v2)<=1e-5);
				if(f1 && f2){
					add = 0;
					break;
				}
			}
			ans += add;
		}
		// int idx;
		// map<int,int>to;
		// sort(tmp1.begin(),tmp1.end());
		// for(int i=0;i<tmp1;i++){
			// int j = i;
			// while(j<tmp1.size() && abs(tmp1[i]-tmp1[j])<=eps){
				// to[tmp1[j]] = idx;
			// }
			// i = j-1;
			// idx ++;
		// }
// 		
		// sort(tmp.begin(),tmp.end(),greater<array<double,2>>());
		// set<int>nums;
		// // for(auto it:tmp){
			// // int flag = 1;
			// // if(nums.lower_bound(it[1])!=nums.end()) flag = 0;
			// // auto it1 = nums.lower_bound(it[1]);
			// // if(it1!=nums.begin()){
				// // it1--;
				// // if(fabs((*it1) - it[1]) <= 1e-5) flag = 0;
			// // }
			// // ans += flag;
		// // }
	}
	cout<<ans+1;
}

// (4,0) (3,5)

// (3,1)

// (-1,1) (0,-4)

//  y1/x1 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: