QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307032 | #7906. Almost Convex | icesmoke | WA | 400ms | 4228kb | C++14 | 4.4kb | 2024-01-17 20:14:13 | 2024-01-17 20:14:13 |
Judging History
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
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: 3556kb
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: 3512kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3632kb
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: 3640kb
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: 400ms
memory: 4228kb
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'