Submission #2210201
Source Code Expand
#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
template<typename T>
void print_to(std::ostream &os,const char *,const char *tail,const T &fst){
os<<fst<<tail;
}
template<typename Fst,typename... Rst>
void print_to(std::ostream &os,const char *del,const char *tail,const Fst &fst,const Rst &... rst){
os<<fst<<del;
print_to(os,del,tail,rst...);
}
template<typename Iter>
void print_to_(std::ostream &os,const char *del,const char *tail,Iter bgn,Iter end){
for(Iter it=bgn;it!=end;){
os<<*it;
if(++it!=end)os<<del;
else os<<tail;
}
}
template<typename Fst,typename... Rst>
void println(const Fst &fst,const Rst &... rst){
print_to(std::cout,"\n","\n",fst,rst...);
}
template<typename Fst,typename... Rst>
void print(const Fst &fst,const Rst &... rst){
print_to(std::cout," ","\n",fst,rst...);
}
template<typename Iter>
void println_(Iter bgn,Iter end){
print_to_(std::cout," ","\n",bgn,end);
}
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const double PI=acos(-1.0);
const double EPS=1e-10;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
ll x[2001],y[2001];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout<<fixed;
#ifdef LOCAL_DEFINE
FILE *stream1;
//FILE *stream2;
stream1=freopen("in","r",stdin);
//stream2=freopen("out","w",stdout);
if(stream1==NULL)return 0;
//if(stream2==NULL)return 0;
#endif
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
ll ans1=0,ans2=0,ans3=0;
for(int i=0;i<n;i++){
vector<double> v;
for(int j=0;j<n;j++){
if(i==j)continue;
v.push_back(atan2(y[j]-y[i],x[j]-x[i]));
}
sort(v.begin(),v.end());
for(int j=0;j<n-1;j++){
v.push_back(v[j]+2*PI);
}
for(int j=0;j<n-1;j++){
int a=lower_bound(v.begin(),v.end(),v[j]+PI/2-EPS)-v.begin();
int b=upper_bound(v.begin(),v.end(),v[j]+PI/2+EPS)-v.begin();
int c=lower_bound(v.begin(),v.end(),v[j]+PI)-v.begin();
ans2+=b-a;
ans3+=c-b;
}
}
ans1=(ll)n*(n-1)*(n-2)/6-ans2-ans3;
print(ans1,ans2,ans3);
#ifdef LOCAL_DEFINE
cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
fclose(stream1);
//fclose(stream2);
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 三角形の分類 |
User |
aim_cpo |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2404 Byte |
Status |
AC |
Exec Time |
755 ms |
Memory |
384 KB |
Judge Result
Set Name |
sample |
subtask01 |
subtask02 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
subtask01 |
01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-handmade00.txt, 01-handmade01.txt, 01-handmade02.txt, 01-handmade03.txt, 01-handmade04.txt, 01-handmade05.txt, sample-01.txt, sample-02.txt |
subtask02 |
01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-handmade00.txt, 01-handmade01.txt, 01-handmade02.txt, 01-handmade03.txt, 01-handmade04.txt, 01-handmade05.txt, 02-00.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-handmade00.txt, 02-handmade01.txt, 02-handmade02.txt, 02-handmade03.txt, 02-handmade04.txt, 02-handmade05.txt, sample-01.txt, sample-02.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-00.txt |
AC |
1 ms |
256 KB |
01-01.txt |
AC |
1 ms |
256 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
AC |
1 ms |
256 KB |
01-04.txt |
AC |
1 ms |
256 KB |
01-05.txt |
AC |
1 ms |
256 KB |
01-06.txt |
AC |
1 ms |
256 KB |
01-07.txt |
AC |
3 ms |
256 KB |
01-08.txt |
AC |
3 ms |
256 KB |
01-09.txt |
AC |
3 ms |
256 KB |
01-10.txt |
AC |
3 ms |
256 KB |
01-11.txt |
AC |
3 ms |
256 KB |
01-12.txt |
AC |
3 ms |
256 KB |
01-13.txt |
AC |
3 ms |
256 KB |
01-14.txt |
AC |
3 ms |
256 KB |
01-15.txt |
AC |
3 ms |
256 KB |
01-16.txt |
AC |
3 ms |
256 KB |
01-17.txt |
AC |
3 ms |
256 KB |
01-18.txt |
AC |
3 ms |
256 KB |
01-19.txt |
AC |
3 ms |
256 KB |
01-handmade00.txt |
AC |
2 ms |
256 KB |
01-handmade01.txt |
AC |
3 ms |
256 KB |
01-handmade02.txt |
AC |
2 ms |
256 KB |
01-handmade03.txt |
AC |
3 ms |
256 KB |
01-handmade04.txt |
AC |
3 ms |
256 KB |
01-handmade05.txt |
AC |
3 ms |
256 KB |
02-00.txt |
AC |
8 ms |
256 KB |
02-01.txt |
AC |
29 ms |
256 KB |
02-02.txt |
AC |
29 ms |
256 KB |
02-03.txt |
AC |
89 ms |
256 KB |
02-04.txt |
AC |
89 ms |
256 KB |
02-05.txt |
AC |
89 ms |
256 KB |
02-06.txt |
AC |
183 ms |
256 KB |
02-07.txt |
AC |
183 ms |
256 KB |
02-08.txt |
AC |
183 ms |
384 KB |
02-09.txt |
AC |
182 ms |
256 KB |
02-10.txt |
AC |
183 ms |
384 KB |
02-11.txt |
AC |
183 ms |
256 KB |
02-12.txt |
AC |
183 ms |
384 KB |
02-13.txt |
AC |
753 ms |
384 KB |
02-14.txt |
AC |
754 ms |
384 KB |
02-15.txt |
AC |
753 ms |
384 KB |
02-16.txt |
AC |
755 ms |
384 KB |
02-17.txt |
AC |
753 ms |
384 KB |
02-18.txt |
AC |
754 ms |
384 KB |
02-19.txt |
AC |
752 ms |
384 KB |
02-handmade00.txt |
AC |
352 ms |
384 KB |
02-handmade01.txt |
AC |
754 ms |
384 KB |
02-handmade02.txt |
AC |
418 ms |
384 KB |
02-handmade03.txt |
AC |
753 ms |
384 KB |
02-handmade04.txt |
AC |
755 ms |
384 KB |
02-handmade05.txt |
AC |
754 ms |
384 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |